자료구조 선택 가이드 — 시간 복잡도와 상황별 최선의 선택

🎯 이 강의에서 배우는 것

자료구조를 배웠다면 이제 언제 어떤 것을 쓸지 알아야 합니다. 리스트를 쓸지, 딕셔너리를 쓸지, 셋을 쓸지 — 그 선택이 프로그램의 속도를 수백 배 바꿉니다. 시간 복잡도를 이해하고 실전 문제에서 최적의 자료구조를 고르는 능력을 기릅니다.

📊 Big-O 표기법 — 성장률로 성능을 비교

import time

# n = 100,000일 때 각 복잡도가 의미하는 연산 횟수
n = 100_000
print(f"O(1):       {1:,}회")
print(f"O(log n):   {n.bit_length():,}회 (약 {n.bit_length()})")
print(f"O(n):       {n:,}회")
print(f"O(n log n): {n * n.bit_length():,}회")
print(f"O(n^2):     {n**2:,}회")
# O(n^2)는 100억회! — 현실적으로 불가능

# 실제 속도 차이 측정
import timeit

data = list(range(n))
target = n - 1   # 최악의 경우

# O(n): 리스트 탐색
t_list = timeit.timeit(lambda: target in data, number=100)

# O(1): 셋 탐색
data_set = set(data)
t_set = timeit.timeit(lambda: target in data_set, number=100)

print(f"리스트 탐색: {t_list:.4f}초")
print(f"셋 탐색:     {t_set:.6f}초")
print(f"셋이 {t_list/t_set:.0f}배 빠름")

📋 자료구조별 시간 복잡도 총정리

연산	list	dict/set	deque	tuple
인덱싱 a[i]	O(1)	-	O(n)	O(1)
탐색 x in a	O(n)	O(1)평균	O(n)	O(n)
끝에 추가	O(1)분할상환	O(1)평균	O(1)	-
앞에 추가	O(n)	-	O(1)	-
임의 위치 삽입	O(n)	-	O(n)	-
끝 삭제	O(1)	O(1)평균	O(1)	-
앞 삭제	O(n)	-	O(1)	-
길이 len()	O(1)	O(1)	O(1)	O(1)
정렬	O(n log n)	-	-	-

🎯 실전 선택 기준

import sys

# 자료구조 선택 결정 트리:
# Q1: 순서가 중요한가? (인덱스로 접근)  → list 또는 tuple
# Q2: 빠른 멤버십 테스트가 필요한가?    → set 또는 dict
# Q3: 키-값 쌍인가?                     → dict
# Q4: 불변이어야 하는가?                 → tuple 또는 frozenset
# Q5: 양쪽 끝 삽입/삭제가 빈번한가?     → deque
# Q6: 빈도 카운팅/그루핑이 필요한가?    → Counter 또는 defaultdict

# 메모리 비교
empty_list = []
empty_dict = {}
empty_set = set()
empty_tuple = ()

print(f"빈 list:  {sys.getsizeof(empty_list)} bytes")   # 56
print(f"빈 dict:  {sys.getsizeof(empty_dict)} bytes")   # 64
print(f"빈 set:   {sys.getsizeof(empty_set)} bytes")    # 216
print(f"빈 tuple: {sys.getsizeof(empty_tuple)} bytes")  # 40

# 1000개 원소일 때
import sys
nums_list = list(range(1000))
nums_tuple = tuple(range(1000))
nums_set = set(range(1000))
nums_dict = {i: i for i in range(1000)}

print(f"list 1000: {sys.getsizeof(nums_list):,} bytes")    # 8056
print(f"tuple 1000: {sys.getsizeof(nums_tuple):,} bytes")  # 8040
print(f"set 1000:   {sys.getsizeof(nums_set):,} bytes")    # 32984
print(f"dict 1000:  {sys.getsizeof(nums_dict):,} bytes")   # 36944
# set, dict는 해시 테이블로 메모리를 더 씀 — 속도 vs 메모리 트레이드오프

🔥 실전 문제로 배우는 자료구조 선택

import timeit
from collections import Counter, deque

# 문제 1: Two Sum — 두 수의 합
def two_sum_list(nums, target):
    # O(n^2) — 모든 쌍 확인
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

def two_sum_dict(nums, target):
    # O(n) — dict로 보수 저장
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

nums = list(range(10000))
target = 19999

t1 = timeit.timeit(lambda: two_sum_list(nums, target), number=10)
t2 = timeit.timeit(lambda: two_sum_dict(nums, target), number=10)
print(f"O(n^2) list: {t1:.4f}초")
print(f"O(n) dict:   {t2:.4f}초")

# 문제 2: 애너그램 판별
def is_anagram_sort(s, t):
    return sorted(s) == sorted(t)   # O(n log n)

def is_anagram_counter(s, t):
    return Counter(s) == Counter(t)   # O(n)

print(is_anagram_counter("listen", "silent"))   # True
print(is_anagram_counter("hello", "world"))     # False

# 문제 3: 슬라이딩 윈도우 최근 k개 최대값
def sliding_max(nums, k):
    # deque에 인덱스 저장, 단조 감소 유지
    result = []
    dq = deque()   # 인덱스 저장

    for i, num in enumerate(nums):
        while dq and dq[0] < i - k + 1:
            dq.popleft()   # 윈도우 밖으로 나간 인덱스 제거
        while dq and nums[dq[-1]] < num:
            dq.pop()       # 현재보다 작은 값 제거
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])   # 현재 윈도우 최대값

    return result

print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

🏔️ heapq — 우선순위 큐

import heapq

# 파이썬의 heapq: 최소 힙(min heap)
# 항상 가장 작은 값이 루트(인덱스 0)
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 2)
heapq.heappush(heap, 4)

print(heap[0])           # 1 (최솟값, O(1))
print(heapq.heappop(heap))  # 1 (최솟값 꺼내기, O(log n))
print(heapq.heappop(heap))  # 2
print(heapq.heappop(heap))  # 3

# heapify: 기존 리스트를 힙으로 변환 O(n)
data = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(data)
print(data[0])   # 1

# k개의 최솟값
print(heapq.nsmallest(3, [5, 2, 8, 1, 9, 3]))   # [1, 2, 3]
print(heapq.nlargest(3, [5, 2, 8, 1, 9, 3]))    # [9, 8, 5]

# 최대 힙 구현: 음수로 저장
max_heap = []
for val in [3, 1, 4, 1, 5, 9]:
    heapq.heappush(max_heap, -val)   # 음수로 저장

print(-heapq.heappop(max_heap))   # 9 (최대값)

# 활용: 다익스트라 알고리즘의 핵심 자료구조
# 우선순위 큐로 가장 짧은 거리 노드를 O(log n)으로 추출

⚠️ 자주 하는 실수

• 탐색이 잦은데 list 사용: if x in my_list를 반복하면 O(n)이 쌓입니다. 탐색이 주요 작업이면 set(my_list)로 한 번만 변환 후 O(1) 탐색을 하세요.
• 큐에 list.pop(0) 사용: O(n) 연산입니다. BFS나 FIFO 큐에는 반드시 deque를 사용하세요.
• 정렬된 리스트에서 선형 탐색: 정렬된 데이터라면 bisect 모듈로 O(log n) 이진 탐색을 사용하세요.

📝 정리 및 다음 강의 예고

• 자료구조 선택 = 시간 복잡도 선택. O(1)과 O(n)은 n=10만에서 10만 배 차이.
• 탐색 → set/dict(O(1)), 순서+인덱싱 → list, 양끝 → deque, 우선순위 → heapq.
• Two Sum: list O(n²) vs dict O(n). 자료구조 하나의 선택이 알고리즘 전체를 바꿉니다.

다음 강의: 클래스와 객체 — 객체지향 프로그래밍의 사고방식 전환. 왜 클래스가 등장했는지, 인스턴스가 메모리에서 어떻게 존재하는지 배웁니다.