[알고리즘] 시간복잡도

코딩테스트를 준비하다 보면 빠지지 않고 등장하는 개념이 있다. 바로 시간복잡도이다. 문제를 풀 때 정답을 맞추는 것도 중요하지만, 주어진 시간 안에 효율적으로 해결하는 것도 필수이기 때문이다. 이번 글에서는 코딩테스트에서 왜 시간복잡도가 중요한지, 어떤 기준으로 따지는지, 그리고 세 가지 유형으로 정의되는 시간복잡도 표기법(Big-O, Big-Theta, Big-Omega)까지 정리해본다.

---

시간복잡도란?

시간복잡도란, 입력 크기(n)가 커질 때 알고리즘이 수행하는 연산 횟수가 얼마나 증가하는지를 나타내는 척도이다. 쉽게 말해, 데이터가 많아질수록 이 코드가 얼마나 느려질지를 수치화한 개념이다.  
코딩테스트에서는 보통 아래 세 가지 표기법을 알아두면 된다.

1. Big-O 표기법 (\(O\))

가장 많이 쓰는 표기법으로, 최악의 경우에 대한 상한선을 의미한다. "아무리 느려도 이 정도보다 더 느리진 않다"라는 걸 나타낸다.
예를 들어 \( O(n^2)\)은 "최악의 경우에도 시간복잡도는 \(n^2\)이하"라는 의미다.

2. Big-Theta 표기법 (\( \Theta \))

정확한 시간복잡도를 나타낸다. 최악도, 최선도 아닌 실제 실행시간이 정확히 이 정도다라고 할 때 쓴다.  
알고리즘 분석에서는 유용하지만, 코딩테스트에서는 많이 쓰이지 않는다.
예를 들어 \( \Theta(n \log {n})\)은 실제로 걸리는 시간이 \( n \log {n} \)정도로 수렴한다는 의미이다.

3. Big-Omega 표기법 (\( \Omega \))

최선의 경우에 대한 하한선을 의미한다. "아무리 빨라도 이 정도 시간은 걸린다"는 뜻이다.  
이것도 코딩테스트보다는 알고리즘 이론 공부할 때 더 자주 등장한다.

예를 들어 \( \Omega (n) \)은 "아무리 최적화해도 최소한 \(n\)번은 계산해야 한다"는 의미다.

정리하면

유형	의미	코딩테스트에서의 중요도
\(O\) (Big-O)	최악의 경우 상한선	★★★★★
\(\Theta\) (Big-Theta)	정확한 시간복잡도	★☆☆☆☆
\(\Omega\) (Big-Omega)	최선의 경우 하한선	★☆☆☆☆

 

시간복잡도의 중요성

코딩테스트에서 제한시간은 보통 1~2초다. 이 시간 안에 프로그램이 끝나려면, 데이터 크기에 맞는 효율적인 알고리즘을 선택해야 한다.  
예를 들어, 입력 크기가 100만개(n=1,000,000)라면 다음과 같은 시간복잡도 기준으로 판단할 수 있다.

- \( O(n \log n) \)이하: 현실적으로 통과 가능
- \( O(n^2) \)이상: 사실상 시간 초과

시간복잡도를 신경쓰지 않고 구현하면, 정답은 맞추더라도 시간 초과로 탈락할 가능성이 높다. 결국 효율적인 알고리즘을 선택하는 게 코딩테스트의 핵심이다.

실전에서 시간복잡도 따지는 법

1. 반복문 개수 체크

단순히 반복문 하나면 \( O(n) \), 중첩되면 \( O(n^2) \), 더 깊으면 \( O(n^3) \)으로 볼 수 있다. 단순한 반복문이 여러 개 돌아가는 구조이면 큰 문제가 되지 않는다. 중요한 것은 중첩 즉, 반복문 안에 반복문이 들어있는 경우이다.
   
2. 데이터 크기 확인  
문제에서 n이 1,000만 이상이면 \(O(n)\) 이하로 풀어야 한다.
   
3. 라이브러리 함수 시간복잡도 파악
예를 들어, Python의 `sort()`는 \( O(n \log n) \)이다. 이런 기본 함수들의 시간복잡도도 알아두면 좋다.

4. 시간 제한과 연산 횟수 감 잡기
보통 1초에 약 1억 번 연산을 할 수 있다고 본다. 시간복잡도 계산 후, 최악의 경우 연산 횟수가 1억을 넘는지 가늠해보면 좋다.

---

시간복잡도는 단순히 알고리즘 이론 공부에서 끝나는 개념이 아니다. 실제 코딩테스트에서 풀어야 하는 문제를 보고, 최적의 알고리즘을 선택하고, 구현한 코드가 제한시간 안에 돌아가는지 예측하는 감각을 기르는 데 반드시 필요한 개념이다. 시간복잡도 감각을 키우면 자연스럽게 알고리즘 문제 해결 능력도 올라간다.