어떤 알고리즘으로 풀어야 할까?

[fkdl0048]

어떤 알고리즘으로 풀어야 할까?

알고리즘 선택의 기준이 되는 시간 복잡도

코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것이다.

시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다. 일반적으로 C++에서는 1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다.

• 시간 복잡도 표기법
  • 빅-오메가(Big-Omega): 최선의 경우
  • 빅-세타(Big-Theta): 평균적인 경우
  • 빅-오(Big-O): 최악의 경우

코딩테스트에서는 빅-오(Big-O) 표기법을 사용한다.

시간 복잡도 활용하기

버블정렬, 병합정렬의 시간 복잡도를 각각 O(N^2), O(NlogN)이라고 표현할 때 다음과 같은 문제가 있다.

• N(1 <= N <= 1,000,000)
• 시간 제한 2초

앞서 말한 것처럼 1억 번의 연산을 1초의 수행 시간으로 예측할 수 있기에 이를 바탕으로 적합성을 평가할 수 있다.

• 버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 -> 부적합
• 병합 정렬 = 1,000,000 * log(1,000,000) = 20,000,000 -> 적합

상수는 무시하면 된다. 예를 들어 1000N은 N으로 표현할 수 있다.