시간복잡도와 공간복잡도 이해하기

자료구조와 알고리즘을 배우기 전에, 딱 하나 먼저 잡고 가야 할 감각이 있습니다. "이 코드는 얼마나 빠른가, 얼마나 메모리를 쓰는가?" 를 가늠하는 눈이에요.

코딩테스트에서 "정답인데 시간 초과"가 나는 이유의 8할이 여기 있습니다. 답만 맞으면 되는 게 아니라, 정해진 시간·메모리 안에 답을 내야 하거든요. 그 기준을 재는 자가 바로 복잡도입니다.

이 한 챕터에서 배우는 것:

시간복잡도가 뭔지, 왜 "초"가 아니라 Big-O로 재는지
자주 나오는 복잡도들 (O(1) ~ O(n²))과 그 감각
공간복잡도 — 메모리도 자원이다
문제를 보고 "이 정도면 통과하겠다"를 어림하는 법

왜 "몇 초"로 안 재고 Big-O로 재나요?

같은 코드도 빠른 컴퓨터에선 0.1초, 느린 컴퓨터에선 0.5초가 걸립니다. 실행 시간(초)은 컴퓨터마다 달라서 알고리즘의 좋고 나쁨을 재는 잣대가 못 됩니다.

그래서 초 대신 "입력이 커질 때 연산 횟수가 어떻게 늘어나는가" 를 봅니다. 이게 컴퓨터와 무관한 알고리즘 고유의 성질이에요. 이걸 표현하는 게 Big-O 표기법입니다.

핵심은 "입력 크기 n에 대해, 최악의 경우 대략 몇 번 일하는가" 입니다.

# 리스트에서 첫 번째 원소 꺼내기 — n이 아무리 커도 딱 1번
def first(arr):
    return arr[0]        # O(1)

# 리스트를 처음부터 끝까지 훑기 — n에 비례해서 n번
def total(arr):
    s = 0
    for x in arr:        # n번 반복
        s += x
    return s             # O(n)

first는 리스트가 10개든 100만 개든 한 번에 끝납니다 → O(1). total은 원소 수만큼 도니까 n에 비례 → O(n).

💡 Big-O는 상수와 낮은 항을 버립니다. 2n + 5번 일해도 그냥 O(n) 이에요. n이 아주 커지면 계수 2나 상수 5는 티가 안 나고, "n에 비례해서 는다"는 성장 속도만 중요하기 때문입니다.

자주 나오는 복잡도들

작은 것부터 큰 것 순서로, 이름과 감각만 잡아두세요.

표기	이름	한 줄 감각	예시
O(1)	상수	입력과 무관, 항상 몇 번	리스트 인덱싱 `arr[i]`, dict 조회
O(log n)	로그	매번 절반씩 줄임	이진 탐색
O(n)	선형	한 번 쭉 훑음	리스트 전체 순회, `x in list`
O(n log n)	선형로그	정렬의 벽	`sorted()`, 병합정렬
O(n²)	이차	이중 반복문	모든 쌍 비교, 버블정렬

숫자로 보면 차이가 확 와닿습니다. n = 1,000,000일 때 대략:

복잡도	연산 횟수 (n=100만)
O(1)	1
O(log n)	약 20
O(n)	1,000,000
O(n log n)	약 2,000만
O(n²)	1조 😱

💡 보통 컴퓨터는 1초에 약 1억(10⁸) 번 연산합니다. 위 표에서 O(n²)의 1조는 1초에 절대 못 끝내죠. "n이 100만인데 이중 반복문(O(n²))을 돌린다" → 시간 초과 확정입니다. 이 어림이 실전에서 제일 자주 씁니다.

이중 반복문은 왜 O(n²)일까

# 모든 쌍 (i, j)을 다 보는 코드
def all_pairs(arr):
    n = len(arr)
    for i in range(n):        # n번
        for j in range(n):    #   각각 n번
            print(arr[i], arr[j])   # → n × n = n² 번 실행

바깥이 n번, 그 안에서 또 n번. 곱해서 n². 반복문이 중첩될 때마다 지수가 하나씩 올라간다고 보면 됩니다.

공간복잡도

시간만 자원이 아닙니다. 메모리도 정해진 한도가 있어요. 공간복잡도는 "입력 크기 n에 대해 추가로 얼마나 많은 메모리를 쓰는가" 를 같은 Big-O로 잰 겁니다.

# 합만 구함 — 변수 하나만 씀. 입력이 커져도 추가 메모리는 그대로
def total(arr):
    s = 0                 # 공간 O(1)
    for x in arr:
        s += x
    return s

# 두 배로 만든 새 리스트 — 입력 n에 비례해 메모리 사용
def doubled(arr):
    result = []           # n개를 새로 담을 공간
    for x in arr:
        result.append(x * 2)
    return result         # 공간 O(n)

total은 아무리 큰 리스트가 들어와도 변수 s 하나뿐 → 공간 O(1). doubled는 입력만큼 새 리스트를 만드니 → 공간 O(n).

💡 소수 챕터의 에라토스테네스의 체를 떠올려 보세요. [True] * (N+1) 로 N칸짜리 리스트를 만들었죠? 그건 시간은 빠르지만 공간을 O(N) 쓰는 겁니다. 흔히 "메모리를 더 써서 시간을 버는" 맞바꿈(trade-off)이 일어나요. 자료구조를 배우는 게 바로 이 맞바꿈을 잘하기 위해서입니다.

실전 감각

문제를 받으면 입력 크기(n의 최댓값) 를 먼저 봅니다. 거기서 "허용되는 복잡도"가 거꾸로 정해져요. (1초 = 약 1억 번 기준)

n의 최댓값	통과 가능한 복잡도	떠올릴 접근
n ≤ 1,000,000	O(n), O(n log n)	한 번 훑기, 정렬
n ≤ 100,000	O(n log n)	정렬, 이진 탐색
n ≤ 10,000	O(n²)까지 OK	이중 반복문 허용
n ≤ 500	O(n³)도 가능	삼중 반복문
n ≤ 20~30	O(2ⁿ)	완전탐색, 백트래킹

💡 이 표를 거꾸로 읽는 게 실전 요령이에요. "n이 10만이네 → O(n²)은 100억이라 시간 초과 → O(n log n) 이하로 풀어야겠다" 처럼, 문제의 제약이 어떤 알고리즘을 써야 하는지 힌트를 줍니다. 복잡도를 알면 문제를 보자마자 방향이 좁혀져요.

정리

개념	한 줄 요약
Big-O	입력 n이 커질 때 연산이 어떻게 늘어나는지의 성장 속도
시간복잡도	몇 번 일하는가 (속도)
공간복잡도	얼마나 메모리를 쓰는가
1초 ≈ 1억 번	시간 초과 여부를 어림하는 기준
시간 ↔ 공간	메모리를 더 써서 속도를 버는 맞바꿈이 흔함

💡 앞으로 모든 챕터에서 코드마다 "이건 O(몇)이지?"를 습관처럼 떠올리세요. 자료구조를 고르는 것도, 알고리즘을 최적화하는 것도 결국 복잡도를 줄이는 일입니다. 이 감각 하나가 "답은 맞는데 시간 초과"를 "통과"로 바꿔줍니다.

직접 풀어보기

다음 각 코드의 시간복잡도를 말해보세요. (a) 리스트의 최댓값을 for로 한 번 훑어 찾기 → ? (b) 리스트의 모든 두 원소 쌍의 합을 출력 (이중 for) → ? (c) sorted(arr) 로 정렬 후 첫 원소 반환 → ?
n = 50,000인 문제에서 이중 반복문(O(n²)) 을 쓰면 대략 몇 번 연산할까요? 1초(약 1억 번) 안에 들어올까요?
어떤 함수가 입력 리스트를 그대로 두고 같은 크기의 새 리스트를 만들어 반환합니다. 이 함수의 공간복잡도는 O(몇)일까요?