더북(TheBook)

최근에는 컴퓨터나 컴파일러(그리고 그 외의 장치들)의 성능이 매우 좋아지면서 1초에 약 10억 회 정도까지 연산이 가능한데, 문제 출제자 또한 이를 고려합니다. 만약 응시자가 제출한 코드의 시간 복잡도가 O(n)이라면 조금 비효율적인 코드라고 통과할 수 있지만, 시간 복잡도가 O(n2)이라면 어떻게 최적화해도 통과할 수 없도록 문제를 설계합니다(설명할 때는 이해하기 쉽도록 10의 제곱 형태로 맞아 떨어지는 입력 개수를 예로 들었으나, 실제 문제에서는 특정 시간 복잡도 이하만 가능하도록 입력 개수가 절묘하게 정해져서 제시됩니다).

그러므로 결국 1초에 1억 번 만큼은 아니더라도 그 이상 연산되면 실패하기 때문에 일종의 용어처럼 사용됩니다. 아무리 코드를 최적화하더라도 근본적인 알고리즘이 틀리면 어떤 방법을 써도 통과할 수 없습니다. 따라서 입력 데이터와 연산 횟수를 고려해서 시간 제한을 넘기지 않는 알고리즘을 선택하는 게 중요합니다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.