문제를 보고 효율적인 풀이를 바로 떠올리기 어렵다면 문제에서 주어진 입력 조건을 이용하여 풀이의 시간 복잡도를 먼저 유추해보는 것도 풀이를 생각해내기에 좋은 힌트가 될 수 있습니다. 시간 제한이 1초일 경우에 유추 가능한 시간 복잡도를 살펴봅시다.
▼ 표 2-3 제한 시간이 1초일 때 유추 가능한 시간 복잡도와 알고리즘
|
N |
유추 가능한 시간 복잡도 |
유추 가능한 알고리즘 |
|
10 |
O(N!) |
순열 |
|
20 |
O(2N) |
조합 |
|
1,000~ |
O(N3), O(N3 logN) |
완전 탐색, 이진 탐색 |
|
10,000~ |
O(N logN) |
정렬, 이진 탐색 |
이처럼 시간 복잡도를 이용하면 문제에서 주어진 조건으로 풀이에 대한 힌트를 얻을 수 있습니다. 하지만 시간 복잡도와 상관없이 작은 입력 제한을 주는 문제도 나올 수 있으므로 유추 가능한 알고리즘은 어디까지나 힌트로 사용해야 합니다. 무조건 해당 알고리즘을 사용하여 문제를 해결해야 한다는 의미가 아니라는 점을 기억합니다.