코딩 테스트는 결국 정확함과 효율성의 싸움이다.
정답을 맞히는 것도 중요하지만, 문제의 시간 복잡도를 고려하고 그에 맞는 알고리즘을 선택해 효율적인 코드를 작성해야한다.
시간 복잡도란?
시간 복잡도는 문제를 해결하기 위해 필요한 연산 횟수를 수학적으로 표현한 것이다.
즉, 코드가 얼마나 많은 계산을 수행하는지를 나타내는 지표다.
코딩 테스트에서는 보통 다음 기준으로 계산한다.
💡 1초 ≈ 1억 번(=10⁸)의 연산
따라서 문제의 제한 시간이 1초일 때, 연산 횟수가 10⁸번을 넘어가면 시간 초과가 발생할 가능성이 높다.
예시로 살펴보기
- 입력 크기 n = 10⁵인 문제에서
알고리즘의 시간 복잡도가 O(n²)라면 약 10¹⁰번의 연산이 필요하다.
→ 1초 안에 끝나지 않는다. - 하지만 O(n log n) 알고리즘이라면 약 10⁶번 정도의 연산으로 충분하다.
→ 1초 안에 통과 가능하다.
이 차이가 바로 시간 복잡도를 고려한 알고리즘 선택의 중요성이다.
시간 복잡도의 세 가지 표기법
시간 복잡도는 입력 크기에 따라 연산 횟수가 어떻게 변하는지를 세 가지 표기법으로 구분한다.
| 표기법 | 의미 | 설명 |
| Ω(n) (빅-오메가) | 최선의 경우 (Best Case) | 입력이 가장 단순할 때 필요한 최소 연산 횟수 |
| Θ(n) (빅-세타) | 평균적인 경우 (Average Case) | 일반적인 상황에서 필요한 평균 연산 횟수 |
| O(n) (빅-오) | 최악의 경우 (Worst Case) | 입력이 가장 복잡할 때 필요한 최대 연산 횟수 |
코딩 테스트에서는 ‘빅-오(O)’가 핵심이다
실제 개발에서는 평균적인 성능도 중요하지만,
코딩 테스트에서는 최악의 경우를 기준으로 생각하는 것이 필수다.
테스트 케이스는 대부분 가장 복잡한 입력까지 포함되기 때문에,
시간 복잡도를 평가할 때는 항상 빅-오(O) 를 기준으로 계산해야 한다.
예를 들어, 정렬 알고리즘을 비교하면 다음과 같다.
| 알고리즘 | 시간 복잡도 | 설명 |
| 삽입 정렬 | O(n²) | 작은 입력에서는 빠르지만, 입력이 커질수록 급격히 느려진다 |
| 병합 정렬 | O(n log n) | 입력 크기가 커져도 안정적인 성능을 유지한다 |
입력 크기가 커질수록 두 알고리즘의 차이는 훨씬 커진다.
시간 복잡도를 다루는 팁💡
- 입력 크기 제한을 먼저 확인한다.
예: n ≤ 10⁶이라면 O(n log n) 이하의 알고리즘을 선택해야 한다. - 자주 등장하는 알고리즘의 복잡도를 암기한다.
- 정렬: O(n log n)
- 이진 탐색: O(log n)
- 완전 탐색(브루트포스): O(2ⁿ) 또는 O(n!)
- 문제를 풀기 전에 대략적인 시간 계산을 해본다.
“이 알고리즘이면 대략 몇 번의 연산이 필요할까?”
이런 감각을 익히면 시간 초과를 미리 방지할 수 있다.
