collections 모듈 — 고급 자료구조 완전 활용

🎯 이 강의에서 배우는 것

파이썬의 collections 모듈은 내장 자료구조의 한계를 넘어서는 강력한 도구들을 제공합니다. Counter로 빈도를 세고, defaultdict로 KeyError를 없애고, deque로 양쪽 끝 O(1) 연산을 합니다. 이 도구들을 알면 코드가 절반으로 줄고 성능이 크게 향상됩니다.

📊 Counter — 빈도 카운팅의 왕

from collections import Counter

# Counter 생성
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
word_count = Counter(words)
print(word_count)   # Counter({'apple': 3, 'banana': 2, 'cherry': 1})

# 문자 빈도 카운팅
char_count = Counter("mississippi")
print(char_count)   # Counter({'s': 4, 'i': 4, 'm': 1, 'p': 2})

# 가장 흔한 n개
print(char_count.most_common(3))   # [('s', 4), ('i', 4), ('p', 2)]
print(word_count.most_common(1))   # [('apple', 3)]

# 없는 키: 0 반환 (KeyError 없음)
print(word_count["mango"])   # 0

# 산술 연산
c1 = Counter({"apple": 3, "banana": 2})
c2 = Counter({"apple": 1, "cherry": 4})
print(c1 + c2)   # Counter({'apple': 4, 'cherry': 4, 'banana': 2}) ← 합산
print(c1 - c2)   # Counter({'banana': 2, 'apple': 2}) ← 차이 (음수 제거)
print(c1 & c2)   # Counter({'apple': 1}) ← 교집합 (최솟값)
print(c1 | c2)   # Counter({'cherry': 4, 'apple': 3, 'banana': 2}) ← 합집합 (최댓값)

# update와 subtract
c1.update(["apple", "apple", "mango"])
print(c1)   # 카운트 추가됨

c1.subtract(["apple", "apple"])
print(c1)   # 카운트 감소됨 (음수 가능)

# elements(): 카운트만큼 요소 반복
c = Counter({"a": 3, "b": 2})
print(list(c.elements()))   # ['a', 'a', 'a', 'b', 'b']

# 총 개수
print(c.total())   # 5 (Python 3.10+)

🗂️ defaultdict — KeyError 없는 딕셔너리

from collections import defaultdict

# defaultdict(factory): 없는 키에 접근하면 factory()를 호출해 기본값 생성
d_int = defaultdict(int)   # 기본값 0
d_int["apple"] += 1
d_int["banana"] += 3
print(dict(d_int))   # {'apple': 1, 'banana': 3}

# list 팩토리: 그루핑
students = [("A반", "홍길동"), ("B반", "이순신"), ("A반", "강감찬")]
class_students = defaultdict(list)
for cls, name in students:
    class_students[cls].append(name)
print(dict(class_students))   # {'A반': ['홍길동', '강감찬'], 'B반': ['이순신']}

# set 팩토리: 중복 없는 그루핑
tags = [("Python", "programming"), ("Python", "scripting"), ("Java", "programming")]
tag_langs = defaultdict(set)
for lang, tag in tags:
    tag_langs[tag].add(lang)
print(dict(tag_langs))   # {'programming': {'Python', 'Java'}, 'scripting': {'Python'}}

# 중첩 defaultdict
nested = defaultdict(lambda: defaultdict(int))
nested["2024"]["Jan"] += 10
nested["2024"]["Feb"] += 20
print(dict(nested["2024"]))   # {'Jan': 10, 'Feb': 20}

# defaultdict vs dict.setdefault 비교
# dict.setdefault: 키마다 호출 필요
normal = {}
normal.setdefault("a", []).append(1)   # 매번 []를 명시

# defaultdict: 자동으로 처리
d = defaultdict(list)
d["a"].append(1)   # 더 간결

🎯 deque — 양방향 O(1) 큐

from collections import deque
import timeit

# deque: 이중 연결 리스트 + 동적 배열 블록 구조
# 양쪽 끝에서 O(1) 삽입/삭제 (리스트의 insert(0,x), pop(0)는 O(n))
dq = deque([1, 2, 3, 4, 5])

# 오른쪽 (리스트와 동일)
dq.append(6)        # 오른쪽 추가
dq.pop()            # 오른쪽 제거

# 왼쪽 (리스트는 O(n), deque는 O(1)!)
dq.appendleft(0)    # 왼쪽 추가
dq.popleft()        # 왼쪽 제거

print(dq)   # deque([1, 2, 3, 4, 5])

# 성능 비교
n = 100_000
lst = list(range(n))
dq2 = deque(range(n))

t_list = timeit.timeit(lambda: lst.insert(0, -1), number=1000)
t_deque = timeit.timeit(lambda: dq2.appendleft(-1), number=1000)
print(f"list.insert(0): {t_list:.4f}초")
print(f"deque.appendleft: {t_deque:.4f}초")
# deque가 수백 배 빠름!

# rotate: 요소 회전
dq = deque([1, 2, 3, 4, 5])
dq.rotate(2)    # 오른쪽으로 2칸
print(dq)   # deque([4, 5, 1, 2, 3])
dq.rotate(-2)   # 왼쪽으로 2칸
print(dq)   # deque([1, 2, 3, 4, 5])

# maxlen: 슬라이딩 윈도우 (크기 초과 시 반대편 자동 제거)
last3 = deque(maxlen=3)
for i in range(7):
    last3.append(i)
    print(list(last3))
# [0], [0,1], [0,1,2], [1,2,3], [2,3,4], [3,4,5], [4,5,6]

# BFS 큐로 활용
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        node = queue.popleft()   # O(1) — 핵심
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": [], "E": [], "F": []}
print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D', 'E', 'F']

📋 OrderedDict와 ChainMap

from collections import OrderedDict, ChainMap

# OrderedDict: 삽입 순서 유지 + move_to_end()
# Python 3.7+에서 일반 dict도 순서 유지하므로 특별한 경우에만 사용

od = OrderedDict()
od["first"] = 1
od["second"] = 2
od["third"] = 3

od.move_to_end("first")           # "first"를 끝으로
od.move_to_end("third", last=False)  # "third"를 앞으로
print(list(od.keys()))   # ['third', 'second', 'first']

# LRU 캐시 간단 구현
class LRUCache:
    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # 최근 사용으로 표시
        return self.cache[key]

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # 가장 오래된 항목 제거

lru = LRUCache(3)
lru.put(1, "a"); lru.put(2, "b"); lru.put(3, "c")
print(lru.get(1))    # "a" (1번이 최근 사용으로 이동)
lru.put(4, "d")      # 3번 캐시 초과 → 2번 제거
print(lru.get(2))    # -1 (제거됨)

# ChainMap: 여러 딕셔너리를 하나로 묶어 탐색
defaults = {"color": "red", "size": "medium", "weight": 1.0}
user_prefs = {"color": "blue"}   # 사용자 설정 (우선)
env_vars = {"DEBUG": True}

combined = ChainMap(user_prefs, defaults)
print(combined["color"])    # "blue" (user_prefs 우선)
print(combined["size"])     # "medium" (defaults 폴백)

# 파이썬 LEGB 규칙과 동일한 탐색 패턴!
# Local → Enclosing → Global → Built-in

⚠️ 자주 하는 실수

• deque 대신 list를 큐로 사용: BFS에서 queue = [], queue.pop(0)는 O(n). 큐로는 반드시 deque를 사용하고 popleft()를 사용하세요.
• Counter 음수 값 처리: Counter.subtract()는 음수를 허용하지만, Counter - Counter는 음수 결과를 제거합니다. 의도에 맞는 연산을 선택하세요.
• defaultdict를 일반 dict처럼 직렬화: json.dumps(defaultdict(list))는 TypeError. 직렬화 전에 dict(d)로 변환하세요.

📝 정리 및 다음 강의 예고

• Counter: 빈도 카운팅, 최빈값, 산술 연산. 텍스트·통계 분석의 핵심 도구.
• defaultdict: 없는 키에 자동 기본값. 그루핑·카운팅을 간결하게.
• deque: 양쪽 끝 O(1) — 큐·스택·슬라이딩 윈도우에 사용. BFS 필수 자료구조.
• OrderedDict: move_to_end()가 있어 LRU 캐시 구현에 적합.

다음 강의: 자료구조 선택 가이드 — 상황에 따라 list, tuple, dict, set, deque 중 어떤 것을 선택해야 하는지, 시간 복잡도 관점에서 결정하는 방법을 배웁니다.