2.2.3 여러 상황에서의 시간 복잡도 생각해보기

지금부터는 ‘최적화가 중요하다, 알고리즘을 잘 짜는 것이 중요하다’라는 당연하고 중요한 사실에서 약간 벗어나 조금 더 현실적인 이야기를 하려고 합니다.

지금까지 언급한 시간 복잡도는 가장 오래 걸리는 연산의 소요 시간을 기준으로 하며, (입력 개수가 충분히 많기 때문에) 그 이외의 기타 연산들은 실행 시간에 크게 영향을 줄 수 없으므로 계산에 포함하지 않는다고 했습니다. 그래서 정말 이상한 작업을 하는 것이 아니라면 약간 비효율적으로 코드를 짜더라도 충분히 통과합니다. 그럼에도 불구하고 굳이 이렇게 최악을 고려해 시간 복잡도를 예측해보는 이유는 구현한 코드가 제 시간에 실행되지 못해 아예 처음부터 새로 짜는 것보다 낫기 때문입니다.

어떻게 보면 제한된 시간과 입력 개수가 서로 줄다리기하는 것이라고 생각할 수 있습니다. 쉬운 문제는 알고리즘 하나만 잘 선택해도 시간 복잡도 측정이 간단하고 모든 문제 풀이가 끝나지만, 어려운 문제는 데이터의 전처리나 단계적 작업이 필요하므로 한 번에 시간 복잡도를 계산하기 어렵고 정확하지 않은 경우가 많습니다. 이런 상황에서 제한 시간 안에 사용할 수 있는 알고리즘들을 파악할 수 있다면 알고리즘 선택 폭이 굉장히 넓어지고 그동안 기피하기만 했던 기법에도 손댈 수 있을 것입니다.