26. 복잡도와 핵심 자료구조

먼저: 왜 복잡도를 알아야 하나

같은 문제를 푸는 코드도 효율이 천차만별입니다. 데이터가 작을 땐 차이가 없지만, 100만 개가 되면 한 코드는 0.0001초, 다른 코드는 10초가 걸릴 수 있습니다.

시간 복잡도(time complexity)는 "데이터가 커질 때 실행 시간이 어떻게 늘어나는가"를 나타냅니다. 실제 초가 아니라 증가 패턴을 봅니다. 이를 Big-O 표기법으로 적습니다.

극적인 예를 봅시다. 10만 개에서 값을 찾을 때, 리스트와 세트의 검색 속도를 비교하면:

import time

big_list = list(range(100_000))
big_set = set(range(100_000))
target = 99_999

# 리스트에서 검색 (앞에서부터 다 훑음)
start = time.perf_counter()
for _ in range(1000):
    _ = target in big_list
print(f"리스트: {time.perf_counter()-start:.4f}초")    # 약 0.7초

# 세트에서 검색 (해시로 바로)
start = time.perf_counter()
for _ in range(1000):
    _ = target in big_set
print(f"세트: {time.perf_counter()-start:.5f}초")       # 약 0.00008초

세트가 수천 배 빨랐습니다. 자료구조를 잘못 고르면 이만큼 느려집니다.

Big-O 표기법

데이터 개수를 n이라 할 때, 자주 보는 복잡도들입니다(좋은 것부터).

flowchart LR
    O1["O(1)<br/>일정 ⚡"]:::g --> Olog["O(log n)<br/>매우 빠름"]:::g --> On["O(n)<br/>보통"]:::y --> Onlog["O(n log n)<br/>괜찮음"]:::y --> On2["O(n²)<br/>느림 ⚠️"]:::r

    classDef g fill:#b8e6c1,stroke:#34a853,color:#14532d
    classDef y fill:#fff3b0,stroke:#e0a800,color:#5c4500
    classDef r fill:#f4b6b6,stroke:#d64545,color:#7a1f1f

핵심 감각: O(1)과 O(log n)은 빠르고, O(n)은 보통, O(n²)은 데이터가 크면 위험합니다.

# O(1): 인덱스로 바로 접근
my_list[5]
my_dict["key"]

# O(n): 전체를 훑음
for x in my_list: ...
target in my_list      # 리스트 검색은 O(n)!

# O(n²): 반복문 안의 반복문
for x in my_list:
    for y in my_list: ...

자료구조별 복잡도

중급편에서 배운 자료구조들의 주요 연산 복잡도입니다. 선택의 기준이 됩니다.

스택(Stack): 마지막에 넣은 걸 먼저

스택은 LIFO(Last In, First Out, 후입선출) 구조입니다. 접시를 쌓듯, 맨 위(마지막에 넣은 것)부터 꺼냅니다.

stack = []
stack.append(1)     # 쌓기 (push)
stack.append(2)
stack.append(3)
print(stack.pop())  # 3   (맨 위부터)
print(stack.pop())  # 2

리스트의 append(끝에 추가)와 pop(끝에서 제거)으로 스택을 만듭니다. 둘 다 O(1)이라 효율적입니다.

쓰임: 실행 취소(undo), 함수 호출 기록, 괄호 짝 검사, 웹 브라우저 뒤로 가기.

flowchart TD
    P3["push 3"]:::y --> Stack
    subgraph Stack["스택"]
        direction TB
        T["3 ← 맨 위 (먼저 나감)"]:::r
        M["2"]:::data
        B["1 ← 맨 아래"]:::data
    end
    Stack --> Pop["pop → 3"]:::g

    classDef y fill:#fff3b0,stroke:#e0a800,color:#5c4500
    classDef data fill:#a8dadc,stroke:#457b9d,color:#1d3557
    classDef r fill:#f4b6b6,stroke:#d64545,color:#7a1f1f
    classDef g fill:#b8e6c1,stroke:#34a853,color:#14532d

큐(Queue): 먼저 넣은 걸 먼저

큐는 FIFO(First In, First Out, 선입선출) 구조입니다. 줄 서기처럼, 먼저 온 사람이 먼저 처리됩니다.

큐는 리스트로도 만들 수 있지만, 맨 앞 제거(pop(0))가 O(n)이라 느립니다. collections.deque를 쓰면 양끝 모두 O(1)입니다.

from collections import deque

queue = deque()
queue.append("a")        # 뒤에 추가
queue.append("b")
queue.append("c")
print(queue.popleft())   # a   (앞에서 제거, O(1))
print(queue.popleft())   # b

쓰임: 작업 대기열, 너비 우선 탐색(BFS), 프린터 인쇄 대기, 메시지 처리.

deque는 양방향 큐라 양끝에서 넣고 뺄 수 있습니다.

from collections import deque
dq = deque([1, 2, 3])
dq.appendleft(0)     # 앞에 추가 → [0, 1, 2, 3]
dq.append(4)         # 뒤에 추가 → [0, 1, 2, 3, 4]
dq.popleft()         # 앞 제거
dq.pop()             # 뒤 제거

⭐ 이진 탐색: O(log n)의 힘

정렬된 데이터에서 값을 찾을 때, 처음부터 하나씩 보는 대신(O(n)) 반씩 줄여가며 찾으면 훨씬 빠릅니다(O(log n)). 이것이 이진 탐색(binary search)입니다.

숫자 맞히기 게임을 생각하세요. 1~100 중 하나를 맞힐 때, "50?" → "더 큼" → "75?" → "더 작음"... 이렇게 매번 절반을 버리면 7번 안에 맞힙니다. 100개를 하나씩 묻는 것보다 훨씬 빠르죠.

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2      # 가운데
        if arr[mid] == target:
            return mid               # 찾음!
        elif arr[mid] < target:
            low = mid + 1            # 오른쪽 절반으로
        else:
            high = mid - 1           # 왼쪽 절반으로
    return -1                        # 없음

data = list(range(1, 1025))          # 정렬된 1024개
print(binary_search(data, 777))      # 776 (인덱스)

1024개를 찾는 데 단 10단계면 충분합니다(2^10 = 1024). 선형 탐색이라면 최악 1024단계가 필요하죠. 데이터가 100만 개여도 이진 탐색은 약 20단계입니다.

flowchart TD
    Start["1~1024 중 777 찾기"]:::data --> S1["가운데 512 확인<br/>777 > 512 → 오른쪽"]:::proc
    S1 --> S2["513~1024 가운데 확인<br/>절반 버림"]:::proc
    S2 --> S3["계속 절반씩...<br/>10단계 안에 발견 ✅"]:::result

    classDef data fill:#a8dadc,stroke:#457b9d,color:#1d3557
    classDef proc fill:#7fd8d8,stroke:#2a9d8f,color:#14532d
    classDef result fill:#b8e6c1,stroke:#34a853,color:#14532d

나쁜 예 ❌ vs 좋은 예 ✅

# 시나리오: 10만 개 ID 중 특정 ID가 있는지 반복 확인

# ❌ 나쁜 예: 리스트로 포함 확인 (매번 O(n))
ids_list = list(range(100_000))
def exists_slow(target):
    return target in ids_list          # O(n) — 느림

# ✅ 좋은 예: 세트로 포함 확인 (O(1))
ids_set = set(range(100_000))
def exists_fast(target):
    return target in ids_set           # O(1) — 빠름

리스트를 세트로 바꾸는 것만으로 검색이 수천 배 빨라집니다. "포함 확인이 잦으면 세트"를 기억하세요.

이 장에서 배운 것

• 시간 복잡도(Big-O)는 데이터가 커질 때 시간이 늘어나는 패턴이다. O(1)·O(log n)은 빠르고 O(n²)은 위험하다.
• 리스트의 in은 O(n), 세트·딕셔너리의 in은 O(1). 포함 확인이 잦으면 세트를 쓴다.
• 스택은 LIFO(리스트 append/pop), 큐는 FIFO(deque의 append/popleft). 큐는 리스트 대신 deque.
• 이진 탐색은 정렬된 데이터에서 매번 절반을 버려 O(log n)에 찾는다. bisect 모듈로도 쓴다.
• 자료구조·알고리즘 선택이 곧 성능이다. 큰 데이터에서 결정적이다.

🧪 실습 문제

문제 1. 다음 연산들의 시간 복잡도를 적으세요.

(a) my_dict["key"]            (b) target in my_list
(c) my_list[10]               (d) 이중 for 반복문

문제 2. 스택과 큐의 차이를 LIFO/FIFO 용어로 설명하세요.

문제 3. deque를 이용해 큐를 만들고, "손님1", "손님2", "손님3"을 차례로 넣은 뒤 처리 순서대로(먼저 온 순) 두 명을 꺼내 출력하세요.

문제 4. 1부터 1,000,000까지 정렬된 리스트에서 이진 탐색으로 값을 찾는다면, 최악의 경우 대략 몇 단계가 필요할까요? (힌트: 2^20 ≈ 100만)

문제 5. 다음 코드를 더 빠르게 고치세요. (힌트: 자료구조 변경)

allowed = ["admin", "user", "guest", ...]  # 1만 개
def is_allowed(name):
    return name in allowed

<details>

<summary>✅ 정답·해설 보기</summary>

1. (a) O(1) 딕셔너리 조회, (b) O(n) 리스트 검색, (c) O(1) 인덱스 접근, (d) O(n²) 이중 반복.

2. 스택은 LIFO(후입선출)로 마지막에 넣은 것을 먼저 꺼내고, 큐는 FIFO(선입선출)로 먼저 넣은 것을 먼저 꺼냅니다.

3.

from collections import deque
queue = deque()
queue.append("손님1"); queue.append("손님2"); queue.append("손님3")
print(queue.popleft())   # 손님1
print(queue.popleft())   # 손님2

4. 약 20단계. 2^20 ≈ 100만이므로 log₂(1,000,000) ≈ 20입니다. 선형 탐색의 최악 100만 단계와 비교하면 엄청난 차이입니다.

5.

allowed = {"admin", "user", "guest", ...}   # 리스트 → 세트
def is_allowed(name):
    return name in allowed                   # O(n) → O(1)

세트로 바꾸면 포함 확인이 O(1)이 됩니다.

</details>

◀️ 이전 장: 25. async와 await ｜ ▶️ 다음 장: 27. 이진 트리