2.1.3 시간 복잡도 선택 시 참고할 만한 사항

지금까지의 설명으로 코딩 테스트는 단순히 빨리 풀려고 노력하는 것이 아니라 문제를 읽고, 입력 데이터 수를 확인한 다음, 요구 사항을 만족시킬 알고리즘이 무엇인지 고민해야 한다는 것을 알았습니다. 하지만 막 코딩 테스트에 입문한 상황에서는 어떤 기준으로 선택해야 하는지 막막할 수 있습니다. 따라서 시간 복잡도를 선택하는 데 도움될 수 있는 몇 가지 사항을 소개하겠습니다. 더 필요한 설명은 나중에 하나씩 알려드릴 예정입니다.

문제를 어떻게 풀지 생각하고 코드를 최적화하는 것은 경험의 영역이지만, 문제를 해석하여 어떻게 풀지 전략을 짜는 것은 지식의 영역입니다. 어떤 방법을 사용할지 선택하기 어렵다면 사전 지식을 활용하여 필요 없는 방법은 과감하게 배제하는 게 시간을 많이 줄일 수 있습니다.

1. 최대 시간이 1초일 때 입력 데이터 수에 따른 시간 복잡도