01. 시간복잡도 (Time Complexity)
백준 대부분 문제는 시간·메모리 제한이 있어 비효율 알고리즘은 통과하지 못합니다. Big-O를 익혀 짜기 전에 통과 가능성을 예측하는 습관을 만듭니다.
이 강의에서 배우는 것
- 1Big-O 표기법의 의미와 주요 복잡도 클래스를 설명할 수 있다.
- 2주어진 코드 조각의 시간복잡도를 분석할 수 있다.
- 3백준 문제의 입력 크기(N)를 보고 적절한 알고리즘 복잡도를 판단할 수 있다.
소개
알고리즘 문제를 풀 때 '정확한 답'을 내는 것만큼 중요한 것이 **얼마나 빠르게** 답을 내느냐입니다. 백준 온라인 저지(BOJ)의 대부분 문제는 시간 제한(1~2초)과 메모리 제한(128~256MB)이 있어, 비효율적인 알고리즘은 통과하지 못합니다. 시간복잡도를 이해하면 코드를 짜기 전에 '이 풀이가 통과할 수 있을까?'를 미리 예측할 수 있습니다.
핵심 개념
1. Big-O 표기법이란?
Big-O는 입력 크기 N이 매우 커질 때, 알고리즘의 실행 시간(또는 메모리 사용량)이 **최악의 경우** 어떻게 증가하는지를 나타내는 표기법입니다. 상수 계수와 낮은 차수의 항은 무시합니다.
예: `3n² + 5n + 7` → **O(n²)**
2. 주요 복잡도 클래스
| Big-O | 이름 | 예시 알고리즘 | N=10⁶일 때 연산 수 (대략) |
|---|---|---|---|
| O(1) | 상수 | 배열 인덱스 접근, 해시 조회 | 1 |
| O(log n) | 로그 | 이진 탐색, 힙 삽입/삭제 | ~20 |
| O(n) | 선형 | 배열 순회, 선형 탐색 | 1,000,000 |
| O(n log n) | 선형로그 | 병합정렬, 힙정렬, `sorted()` | ~20,000,000 |
| O(n²) | 이차 | 버블정렬, 삽입정렬, 이중 루프 | 1,000,000,000,000 |
| O(2ⁿ) | 지수 | 부분집합 완전탐색 | 불가 |
3. 시간 제한과 연산 수
**시간 제한 1초 ≈ 약 1억(10⁸) 연산**
이 기준을 바탕으로 입력 크기에 따라 허용되는 복잡도를 판단합니다:
| N (입력 크기) | 허용 복잡도 (1초 기준) |
|---|---|
| N ≤ 10 | O(2ⁿ), O(n!) |
| N ≤ 20 | O(2ⁿ) |
| N ≤ 500 | O(n³) |
| N ≤ 3,000 | O(n²) |
| N ≤ 100,000 | O(n log n) |
| N ≤ 1,000,000 | O(n) |
| N ≤ 10,000,000 | O(n) (타이트) |
4. 메모리 제한
파이썬에서 정수 리스트 1,000,000개는 약 **8MB** (C/C++ 기준 4MB)를 사용합니다. 파이썬 객체 오버헤드로 인해 실제로는 더 많이 사용되므로 주의해야 합니다.
정수 N개짜리 리스트: 약 8N bytes (int의 경우 파이썬 오버헤드 포함 약 28 bytes/원소)
2차원 N×N 리스트: O(N²) 공간 → N=1000이면 약 8MB5. timeit으로 실제 시간 측정하기
import timeit
# 방법 1: timeit.timeit() — 짧은 코드 스니펫 측정
result = timeit.timeit('sum(range(1000))', number=10000)
print(f'10000번 실행 총 시간: {result:.4f}초')
# 방법 2: time 모듈 — 긴 코드 블록 측정
import time
start = time.perf_counter()
# ... 측정할 코드 ...
elapsed = time.perf_counter() - start
print(f'실행 시간: {elapsed:.6f}초')예제로 보기
예제 1: 각 복잡도 클래스 시각화 (`src/01_big_o_demo.py`)
O(1)부터 O(n²)까지 각 복잡도의 실제 연산 횟수를 출력합니다.
[실행 결과 예시]
O(1) 연산 횟수: 1 (n=100000)
O(log n) 연산 횟수: 17 (n=100000)
O(n) 연산 횟수: 100000 (n=100000)
O(n logn)연산 횟수: 1660964 (n=100000, 예상값)
O(n²) 연산 횟수: 499500 (n=1000)
O(2ⁿ) 연산 횟수: 1048576 (n=20)복잡도 성장 비교 (n=16)
╔═══════════════╦══════════════════════╗
║ Big-O ║ 연산 수 (대략) ║
╠═══════════════╬══════════════════════╣
║ O(1) ║ 1 ║
║ O(log n) ║ 4 ║
║ O(n) ║ 16 ║
║ O(n log n) ║ 64 ║
║ O(n²) ║ 256 ║
║ O(2ⁿ) ║ 65536 ║
╚═══════════════╩══════════════════════╝직접 실행해 보세요:
python src/01_big_o_demo.py예제 2: 실제 시간 측정 (`src/02_time_measure.py`)
`timeit`과 `time` 모듈로 버블정렬(`O(n²)`)과 파이썬 내장 `sorted()`(`O(n log n)`)의 실행 시간을 입력 크기별로 비교합니다.
[실행 결과 예시]
입력 크기 버블정렬(초) sorted()(초) 배율
100 0.001234 0.000023 53.7x
1000 0.125600 0.000310 405.2x
10000 12.340000 0.003500 3525.7xpython src/02_time_measure.py예제 3: 공간복잡도 (`src/03_space_complexity.py`)
`sys.getsizeof`를 이용해 O(1), O(n), O(n²) 공간 사용량을 측정합니다.
python src/03_space_complexity.py예제 4: 선형탐색 vs 이진탐색 (`src/04_complexity_compare.py`)
동일한 데이터에서 선형탐색(O(n))과 이진탐색(O(log n))의 비교 횟수를 카운터로 측정합니다.
python src/04_complexity_compare.py자주 하는 실수
- **O(n²) 풀이를 n=100,000에 적용하기** - n=100,000에서 O(n²)는 약 10¹⁰ 연산 → 시간 초과 필연적 - 이중 루프가 보이면 항상 `n`의 크기를 확인하세요.
- **파이썬은 C++보다 5~10배 느립니다** - 백준 파이썬 시간 제한은 C++의 3~5배 여유를 주는 경우도 있지만, 항상 그렇지는 않습니다. - O(n log n) 풀이로도 PyPy를 사용해야 통과하는 경우가 있습니다.
- **상수를 무시하다 TLE** - O(n)이어도 상수가 크면 느릴 수 있습니다. - 예: 반복문 안에서 문자열 연결(`+=`)은 O(n)처럼 보여도 실제로는 O(n²)입니다.
- **`in` 연산자를 리스트에 사용하기** - `x in list` → O(n), `x in set` → O(1) 평균 - 멤버십 검사가 반복될 때는 반드시 `set`으로 변환하세요.
- **복잡도 분석 없이 제출하기** - 코드를 작성하기 전에 '이 풀이의 복잡도는 O(?)이고, n=?일 때 몇 연산인가?'를 항상 계산하는 습관을 기르세요.
정리
- Big-O는 **최악의 경우** 실행 시간 증가율을 나타냅니다.
- 시간 제한 1초 ≈ 10⁸ 연산을 기준으로 복잡도를 선택합니다.
- 파이썬은 C++보다 느리므로 더 효율적인 알고리즘이 필요할 수 있습니다.
- `in` 연산은 자료구조에 따라 O(n) vs O(1) 차이가 납니다.
직접 해 보기
- `src/01_big_o_demo.py`를 실행하고 n=100일 때 각 복잡도의 연산 수를 기록하세요.
- `src/02_time_measure.py`에서 입력 크기를 100,000으로 늘려보고 버블정렬이 얼마나 걸리는지 확인하세요 (경고: 매우 오래 걸릴 수 있습니다).
- 백준 [1546번 (평균)](https://www.acmicpc.net/problem/1546)을 풀고, 자신의 풀이 복잡도를 분석해 보세요.
- `homework/README.md`의 과제를 완성하세요.