PS. 코딩 테스트 어떤 문제를 풀든 어떠한 방법으로 해결할지 생각하기 마련이다. 지금까지는 제일 간편한 접근으로 문제를 풀어보고, 안되면 다음 방법으로 풀어보고... 이런식으로 해결해왔는데, 시간은 시간대로 쓰고 힘도 힘도 쓰니 조금 미련하게 느껴졌다. 물론 단계별로 접근하는 것은 중요하지만 이제는 좀 경제적인 면도 따져야 할 때가 아닐까 한다.
그런 의미에서 문제에 적혀진 입력값의 범위는 큰 힌트가 되어준다고 한다. 그냥 이론적으로 시간 복잡도를 따질게 아니라 이를 이용해서 어떠한 알고리즘을 적용할 수 있을지 범위를 좁힐 수 있다. 일단 잘 쓰려면 알고리즘들에 대해서 잘 알아야하겠지만 말이다.
기대값을 계산하는 법은 간단하다 일반적인 가정으로 CPU는 1초에 1억(10^8)번 계산할 수 있다고 한다. 따라서 시간 복잡도에 1억에 근사하도록 하는 입력값 N을 구하면 N 크기에 따라 1초안에 풀 수 있는지를 계산할 수 있다. 물론 절대적인 수치는 아니기에 확신은 금물이다.
| O(1) | 상수시간 |
| O(log n) | 10^18 이하 |
| O(n) | 천만~억 (10^7 ~ 10^8) 이하 |
| O(n log n) | 백만 (10^6) 이하 |
| O(n^2) | 10,000 (10^4) 이하 |
| O(n^3) | 500 이하 |
이제 해당하는 알고리즘이 어떤 시간복잡도를 가지고 있는지만 잘 알고만 있으면 된다.