1. 복잡도란?
- 어떤 문제를 얼마나 빨리, 얼마나 효율적으로 푸는가를 나타내는 척도예요.
- 즉, 프로그램이 입력을 받았을 때 시간이 얼마나 걸릴지, 메모리를 얼마나 쓸지를 수학적으로 계산하는 방법이에요.
2. 시간 복잡도 (Time Complexity)
👉 프로그램이 실행될 때 걸리는 시간이 입력 크기에 따라 어떻게 늘어나는지를 보는 것.
예시:
- 배열 길이가 10일 때: for문이 10번 돈다.
- 배열 길이가 100일 때: for문이 100번 돈다.
→ 실행 횟수가 입력 크기 N에 비례하니까
이런 걸 O(N)이라고 적어요.
여기서 O는 "order of"(크기 정도)라는 의미예요.
3. 공간 복잡도 (Space Complexity)
👉 프로그램이 실행될 때 메모리를 얼마나 차지하는지 보는 것.
- 예: 크기 100인 배열을 만든다 → O(N) 공간.
- 그냥 변수 하나만 쓴다 → O(1) 공간.
4. 자주 쓰이는 복잡도 예시
- O(1): 상수 시간 - 입력 크기가 얼마든 항상 같은 시간 (예: 변수에 값 할당하기).
- O(log N): 로그 시간 - 입력을 계속 반으로 나누는 방식 (예: 전화번호부에서 이름 찾기).
- O(N): 선형 시간 - 입력 크기에 비례하는 시간 (예: 배열의 모든 요소 한 번씩 확인하기).
- O(N log N): 선형 로그 시간 - 대부분의 효율적인 정렬 알고리즘이 이 정도 복잡도를 가짐.
- O(N²): 제곱 시간 - 이중 반복문처럼 입력 크기의 제곱만큼 시간이 걸림 (예: 모든 요소 쌍 비교).
- O(2^N): 지수 시간 - 입력이 조금만 커져도 계산 시간이 엄청나게 증가 (예: 모든 부분집합 구하기).
즉, **복잡도(Complexity)**는 "입력이 커질수록 실행 시간이 얼마나 늘어나는가?"를 수학적으로 표현하는 거예요.
쉽게 비유하면:
- O(1): 엘리베이터 버튼 한 번 누르면 바로 도착
- O(N): 계단을 한 칸씩 올라감 → 층이 많을수록 오래 걸림
- O(N²): 계단을 오르는데 매번 내려갔다 다시 올라감 (비효율)
👉 그래서 알고리즘 문제를 풀 때는 "이 코드가 입력이 엄청 커졌을 때도 빠르게 동작할까?"를 보는 거예요.
5. 복잡도 비교하기
입력 크기에 따른 각 복잡도별 실행 시간 비교:
| 입력 크기 (N) |
O(1) |
O(log N) |
O(N) |
O(N log N) |
O(N²) |
O(2^N) |
| 10 |
1 |
3 |
10 |
30 |
100 |
1,024 |
| 100 |
1 |
7 |
100 |
700 |
10,000 |
∞ |
| 1,000 |
1 |
10 |
1,000 |
10,000 |
1,000,000 |
∞ |
| 1,000,000 |
1 |
20 |
1,000,000 |
20,000,000 |
10^12 |
∞ |
👉 이 표를 보면 알 수 있듯이, 복잡도에 따라 처리 시간의 차이가 엄청나게 커질 수 있어요.
6. 알고리즘 선택 시 고려사항
- 시간 복잡도가 낮은 알고리즘이 항상 최선은 아닙니다. 입력 크기가 작을 때는 구현이 간단한 알고리즘이 더 효율적일 수 있어요.
- 상수 계수도 중요합니다. O(N)이 O(N²)보다 항상 빠른 것은 아니에요. 예를 들어 O(100N)과 O(N²)을 비교하면, N이 100보다 작을 때는 O(N²)이 더 빠를 수 있습니다.
- 공간과 시간은 종종 트레이드오프 관계입니다. 메모리를 더 사용하면 시간을 절약할 수 있고, 그 반대도 가능해요.
7. 실전 적용 예시
문제: 배열에서 특정 값 찾기
- 선형 탐색 (O(N)): 처음부터 끝까지 하나씩 비교
- 이진 탐색 (O(log N)): 정렬된 배열에서 중간값과 비교하며 반씩 줄여나감
- 해시 테이블 (O(1)): 미리 해시 테이블에 저장해두고 바로 접근
👉 입력 크기가 클수록 효율적인 알고리즘의 중요성이 커집니다. 웬만한 코딩 테스트에서는 시간 제한이 있기 때문에 복잡도를 고려한 알고리즘 선택이 매우 중요해요!