[코딩테스트] 시간복잡도
“문제 유형만 보면 어떤 알고리즘을 써야 할지 떠오르면 코테는 거의 다 푼 셈이다.”
코딩 테스트를 준비하려고 많은 영상들과 블로그들을 찾아봤다면, 해당 조언을 무조건 한 번은 봤을 것이다!
문제를 해결할 수 있는 알고리즘을 빠르게 떠올리게 된다면 구현 능력을 쉽게 따라 잡을 수 있다고 말하며,
이와 같이 공유되는 문제 유형과 알고리즘을 연결한 표도 함께 보여주곤 한다.
하지만...
코테를 제대로 공부하지 않았을 때 이 표를 보게 되다면
최단 거리, 최적, 최소 단계, 최소 시간, 비용과 같은 단어들이 어디에서 나오는 건지 이해가 잘 안될 것이다...
| 스택 | - 쌍이 맞는지 - 최근 |
- 무언가를 저장하고 반대로 처리해야 할 때 - 데이터의 조합이 균형을 이루어야 할 때 - 알고리즘의 재귀 특성을 가릴 때 - 최근 상태 추적 |
| 큐 | - 순서대로 - 스케줄링 |
- 특정 조건에 따라 시뮬레이션할 때 - 시작 지점부터 목표 지점까지 최단 거리 |
| 깊이 우선 탐색 | - 모든 경로 | - 메모리 사용량이 제한적일 때의 탐색 - 백트래킹 문제를 풀 때 |
| 너비 우선 탐색 | - 최적 - 최소 단계 |
- 시작 지점부터 최단 경로나 최소 횟수를 찾아야 할 때 |
| 백트래킹 | - 조합 - 부분 집합 |
- 조합 및 순열 문제 - 특정 조건을 만족하는 부분 집합 |
| 최단 경로 | - 최소 시간 - 최소 비용 - 음의 순환 |
- 다익스트라: 특정 지점에서 나머지 지점까지 가는 최단 경로 - 벨만-포드: 음의 순환 탐지, 음의 가중치를 가진 그래프에서 최단 경로 |
출처: 코딩테스트 합격자되기 (자바스크립트 편)
표를 이해하고 싶다면, 시간 복잡도를 먼저 알아야 한다!
그래서, 시간 복잡도가 뭔데?
입력 크기 N이 커질 때, 연산 횟수가 어떻게 증가하는 지를 나타내는 지표이다.
예를 들어, 입력이 N = 1000일 때, 알고리즘이 O(N²)라면 연산은 약 1,000,000번 발생하게 된다.
시간 제한이 1초일 경우, 시간 초과가 발생할 수 있다!
문제를 푸는 알고리즘이 아무리 정답이라도, 위의 경우처럼 시간이 너무 오래 걸리면 시간 초과(TLE)가 발생한다.
따라서 시간 복잡도는 알고리즘 선택에 있어 핵심적인 기준이 된다.
시간 복잡도에 대해 개념만 알고 있으면 되는건가?
당연하지만, 그렇지 않다!
시간 복잡도 분석시 꼭 알아야 할 부분은 크게 2가지가 존재한다.
1. 항상 최악의 경우를 기준으로 분석해야 한다.
2. 정확한 연산 횟수 보다는 입력 크기에 따른 추이를 본다. (Big-O 표기법 사용)
- Big-O (빅오): 가장 흔히 쓰이는 표기법. 최고차항만 남기고 계수는 생략
예: 3N2+2N+1→O(N2)3N^2 + 2N + 1 → O(N^2)
빅오 표기법을 활용한 시간 복잡도별 입력 제한 기준은 아래와 같다
| O(N!) | 10 이하 |
| O(2^N) | 20 ~ 25 이하 |
| O(N³) | 200 ~ 300 이하 |
| O(N²) | 3,000 ~ 5,000 이하 |
| O(N log N) | 약 1,000,000 |
| O(N) | 약 10,000,000 ~ 20,000,000 |
| O(log N) | 1,000,000,000 이상도 가능 |
단순히 문제를 많이 푸는 것도 중요하지만,
그보다 더 중요한 것은 문제 분석력이다!
" 이 문제는 어떤 알고리즘으로 접근해야 하지? "
" 이 알고리즘은 시간 초과 없이 실행 가능한가? "
이러한 직관력과 시간 복잡도에 대한 감각을 키우는 것이 좋은 성과를 내기 위한 핵심이다!