시간 복잡도로 알고리즘 고르기: 입력 크기별 기준과 Python 실측
6분 읽기
코딩테스트에서 코드를 쓰기 전에 가장 먼저 할 일은 입력 크기 N을 보고 "어느 정도 복잡도까지 통과하는지"를 정하는 것입니다. 이 판단이 틀리면 풀이가 맞아도 시간 초과로 끝납니다. 이 글에서는 기준표를 먼저 정리하고, 그 기준이 실제로 맞는지 Python 코드를 직접 실행해서 확인합니다.
기준은 "연산 횟수 약 1천만 번"
시간 제한이 1~2초인 문제에서 Python은 대략 1천만 번 안팎의 연산까지 안전하게 처리한다고 보는 것이 관례입니다. 정확한 값은 채점 서버와 연산 종류에 따라 달라서, 이 환경(Python 3.9.6, Apple Silicon Mac)에서 단순 반복문의 속도를 먼저 쟀습니다.
import timeit
def loop(n):
s = 0
for i in range(n):
s += i
return s
t = min(timeit.repeat(lambda: loop(10**7), number=1, repeat=3))
print(f"{t:.3f}초")
실행 결과는 1천만 번 반복에 약 0.19초, 초당 약 5천만 회였습니다. 하지만 실제 문제의 반복문 안에는 리스트 접근, 비교, 함수 호출이 섞여 한 번의 반복이 훨씬 무겁습니다. 그래서 "한 줄짜리 연산이 1천만 번"을 보수적인 상한으로 잡는 것입니다.
입력 크기별 기준표
상한 N에서 연산 횟수가 1천만 근처가 되도록 계산한 표입니다.
| 입력 크기 N | 통과 가능한 복잡도 | 대략의 연산 수 |
|---|---|---|
| 20 이하 | O(2^N) 완전탐색 | 약 100만 |
| 200 이하 | O(N^3) | 800만 |
| 3,000 이하 | O(N^2) | 900만 |
| 50만 이하 | O(N log N) | 약 950만 |
| 1,000만 이하 | O(N) | 1,000만 |
| 그 이상 | O(log N) 또는 수식 | - |
관례적인 기준이므로 반복 안의 연산이 무거우면 한 단계 낮춰서 생각해야 합니다. O(N log N)의 감을 잡는 기준으로, 파이썬 내장 sorted로 무작위 순서의 정수 100만 개를 정렬하는 데 이 환경에서 139.2 ms가 걸렸습니다. 정렬 한 번은 대부분의 문제에서 부담이 아니고, 정렬을 반복문 안에서 N번 부르는 것이 문제입니다.
실측 1: 중복 검사, O(N^2) vs O(N)
리스트에 중복이 있는지 확인하는 두 가지 방법입니다. 중복이 없는 경우가 최악이라서 그 입력으로 쟀습니다.
def has_dup_quadratic(a):
n = len(a)
for i in range(n):
for j in range(i + 1, n):
if a[i] == a[j]:
return True
return False
def has_dup_set(a):
return len(set(a)) != len(a)
3번 실행한 값 중 최솟값입니다.
| n | 이중 반복문 | 증가 배율 | set 방식 |
|---|---|---|---|
| 500 | 3.04 ms | - | 0.0035 ms |
| 1,000 | 11.47 ms | 3.8배 | 0.0050 ms |
| 2,000 | 46.70 ms | 4.1배 | 0.0108 ms |
| 4,000 | 186.25 ms | 4.0배 | 0.0211 ms |
n이 2배가 될 때마다 이중 반복문의 시간은 약 4배가 됩니다. 이것이 O(N^2)의 모양입니다. 이 속도를 그대로 늘려 보면 n이 10만일 때는 n=4,000의 25배라서 시간은 625배, 약 116초가 됩니다(추정값입니다). 1~2초 제한에는 한참 못 미칩니다. 기준표에서 "3,000 이하에서만 O(N^2)"라고 한 이유입니다.
반면 set 방식은 n이 8배가 되는 동안 0.0035 ms에서 0.0211 ms로, 거의 N에 비례해서만 늘었습니다. 다만 n=500에서의 격차(약 870배)에는 알고리즘 차이 외에 set 변환이 C로 구현되어 Python 반복문보다 빠르다는 점도 섞여 있습니다. 두 방식을 비교할 때는 격차 자체보다 증가 패턴이 더 믿을 만한 정보입니다.
실측 2: x in 리스트는 O(N)이다
반복문 안에서 if x in lst를 쓰면 코드는 한 줄이어도 비용은 N입니다. 찾는 값이 없는 최악의 경우를 쟀습니다.
lst = list(range(n))
st = set(lst)
x = -1 # 없는 값
x in lst # 리스트 검색
x in st # 집합 검색
| n | 리스트 1회 | 집합 1회 |
|---|---|---|
| 1,000 | 4.42 µs | 0.0336 µs |
| 10,000 | 44.79 µs | 0.0320 µs |
| 100,000 | 457.65 µs | 0.0287 µs |
| 1,000,000 | 4,654.09 µs | 0.0341 µs |
n이 1,000배가 되는 동안 리스트 검색은 4.42 µs에서 4,654 µs로 약 1,050배가 됐고, 집합 검색은 0.03 µs 근처에서 거의 변하지 않았습니다. 그래서 N번 반복하는 반복문 안에 in 리스트가 들어가면 겉보기에는 O(N)인 코드가 실제로는 O(N^2)이 됩니다. 입력이 10만 개인 문제에서는 이런 한 줄 때문에 시간 초과가 나기 쉽습니다.
집합이 공짜는 아닙니다. 리스트를 집합으로 바꾸는 데 O(N)이 들고, 해시 가능한 값만 담을 수 있으며, 순서와 중복 개수를 잃습니다. 값의 유무만 반복해서 확인할 때 쓰는 도구입니다.
속도를 얻는 대가: 메모리
집합이 빠른 것은 공짜가 아닙니다. 해시 테이블은 빈 칸을 일부러 남겨 두고 값을 흩어서 저장하기 때문에, 같은 원소 수에서 리스트보다 메모리를 더 씁니다. 정수 100만 개를 담은 리스트와 집합의 컨테이너 크기를 sys.getsizeof로 쟀더니 리스트는 약 8.0 MB, 집합은 약 33.6 MB로 4.2배였습니다. 정수 객체 자체의 크기는 두 경우에 같아서 뺀 값입니다. 메모리 제한이 빠듯한 문제에서는 시간 복잡도뿐 아니라 이런 공간 비용도 같이 따져야 합니다.
시간 초과가 났을 때 점검 순서
풀이가 맞는데 시간 초과가 난다면 아래 순서로 확인합니다.
- N의 범위를 다시 읽고, 위 표에서 내 풀이의 복잡도가 허용 범위인지 계산합니다.
- 반복문이 몇 겹 중첩되어 있는지 셉니다. 2겹인데 N이 10만이면 알고리즘을 바꿔야 합니다.
- 반복문 안에
in 리스트, 리스트 슬라이싱, 매번 정렬하는 코드처럼 한 줄이지만 O(N)인 연산이 숨어 있는지 찾습니다. - 그래도 안 되면 그때 입출력 속도 같은 상수 단위의 최적화를 봅니다. 복잡도가 틀린 풀이는 상수를 줄여도 해결되지 않습니다.
정리
- 문제를 읽으면 N의 범위부터 확인합니다.
- 위 표로 허용되는 복잡도를 정하고, 그보다 느린 풀이는 처음부터 고르지 않습니다.
- 반복문 안에
in 리스트처럼 숨은 O(N)이 없는지 확인합니다. - 이 글의 숫자는 Python 3.9.6, macOS(Apple Silicon)에서 잰 값이고 실행할 때마다 조금씩 달라집니다. 변하지 않는 것은 "n이 2배일 때 시간이 몇 배가 되는가"라는 증가 패턴입니다.
복잡도 계산은 풀이를 고르는 첫 단계일 뿐 정답을 보장하지는 않습니다. 허용 범위 안의 풀이를 골랐다면, 그다음에는 작은 입력으로 느리지만 확실한 풀이와 결과를 대조해 맞는지 확인합니다.
다음 글에서는 in 리스트를 해시 맵으로 바꿔 O(N^2) 풀이를 O(N)으로 줄이는 대표 문제를 다룹니다.