[코딩테스트] 시간 제한과 시간 복잡도

시간 제한과 시간 복잡도

• 코딩 테스트의 제한 시간: 보통 `1~5초`
• 1초에 실행 가능한 최대 연산 횟수: 약 `1억 번`
• 알고리즘 선택 기준: 문제의 시간 제한을 고려하여 시간 복잡도를 분석하고 적절한 알고리즘을 선택해야 한다.

 

예시: N의 최대값이 100,000이고 제한 시간이 1초인 경우

- 허용 가능한 최대 연산 횟수: `1억 번`
- 시간 복잡도가 O(N²)일 경우:
    - 연산 횟수 = `100,000 × 100,000 = 100억 번`
    - `1억 번을 초과하므로 사용 불가능`
- 적절한 알고리즘 선택: O(N log N) 이하의 알고리즘을 고려해야 함 (예: 정렬 알고리즘, 이진 탐색 등)

 

1초에 최대 연산 횟수(최대 입력 크기)

시간 복잡도	최대 연산 횟수
O(N)	약 1억번
O(N^2)	약 1만번
O(N^3)	약 500번
O(2^N)	약 20번
O(N!)	10번

 

제한 시간이 1초 일 경우, N의 범위에 따른 시간 복잡도 선택

N의 범위	허용되는 시간 복잡도
500	O(N³) 이하
2,000	O(N²) 이하
100,000	O(N log N) 이하
10,000,000	O(N) 이하
10,000,000,000	O(log N) 이하

이렇게 정리하면, 문제에서 N의 크기를 보고 바로 적절한 알고리즘을 선택할 수 있다.

 

참고

• 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 저