Python 의 dict 와 set: 이미 쓰는 해싱

"해시맵을 만들 필요 없어 — Python 이 세계적인 거 둘을 건네. 능력은 그걸 구현하는 게 아니라; 그것들이 O(n²) 를 O(n) 으로 바꾸는 일상 문제 열두 개를 알아보는 거야."

연산이 다 O(1)

이 트랙의 모든 이론이 여기서 현금화돼. dict 에서: d[k] 읽기, d[k] = v 쓰기, k in d 멤버십, del d[k] — 다 평균 O(1). set 에서: add, remove, x in s — 다 평균 O(1). 집합 대수 (a | b 합집합, a & b 교집합, a - b 차집합) 는 곱이 아니라 집합 크기에 비례한 시간에 돌아. 이게 building block 이고; 예술은 맞는 순간에 손대는 거야.

외울 가치 있는 패턴

중복 제거: set(items) — 고유 원소, 즉시.
멤버십: x in some_list 대신 x in some_set — O(n) 대 O(1), 가장 흔한 속도 향상.
세기: collections.Counter(items) — 한 패스에 각 원소 빈도.
묶기: collections.defaultdict(list) — '이 키가 이미 있나?' 확인 없이 키로 항목 버킷.
캐싱 / 메모이제이션: 입력을 계산된 결과로 매핑하는 dict — Dynamic Programming 트랙의 심장.
two-sum 트릭: 한 패스, 본 걸 dict 에 기억, 보수가 이미 있는지 확인 — O(n²) 대신 O(n).

dict 와 set 은 평균 O(1) 조회, 삽입, 삭제, 멤버십을 줘. 능력은 패턴 인식이야: 중복 제거 → set, 세기 → Counter, 묶기 → defaultdict, '전에 봤나?' → set, '답을 기억' → dict. 그것들로 손대는 게 존재하는 가장 흔한 현실 최적화야.

영원히 값하는 반사신경

지을 습관: 반복문에 if x in a_list 가 있거나, 쌍/매칭을 찾으려 반복문을 중첩할 때마다, set 이나 dict 가 그걸 O(n²) 에서 O(n) 으로 바꾸는지 물어. 거의 늘 그렇고, 거의 늘 작은 변경이야. two-sum 문제가 완벽한 상징이야 — 무차별은 모든 쌍 확인 (O(n²)); dict 버전은 가면서 각 수를 기억하고 보수를 O(1) 에 확인해, 전체를 O(n) 으로 무너뜨려. 같은 답, 다른 구조, 범주적으로 더 빠른 프로그램.

피파의 고백

초반에, 내가 쓴 거의 모든 느린 함수가 같은 병이었어: 반복문 안 in list 확인. 아빠가 로직 리뷰를 멈추고 그냥 그 줄들에 동그라미 치기 시작했어: "set. set. 저건 dict." 고침은 각자 한 단어였고, 몇 초짜리 함수를 일상적으로 즉시로 바꿨어. 반사신경으로 체화했어 — 이젠 반복문 안에서 in 이 리스트를 만나면 작은 경보가 울려. 그 반사신경 하나가 내가 쓴 어떤 영리한 알고리즘보다 많은 런타임을 아꼈을 거야.

Code

Counter, defaultdict, 집합 대수, two-sum·python

from collections import Counter, defaultdict

# 한 패스에 세기 — 수동 'if key in d' 장부 관리 없음.
words = "the cat the dog the bird".split()
print(Counter(words))            # Counter({'the': 3, 'cat': 1, 'dog': 1, 'bird': 1})

# 키로 묶기 — defaultdict 가 '이 키 있나?' 확인을 건너뜀.
animals = ["cat", "cow", "dog", "crow"]
by_first = defaultdict(list)
for a in animals:
    by_first[a[0]].append(a)     # 첫 사용 시 리스트 자동 생성
print(dict(by_first))            # {'c': ['cat','cow','crow'], 'd': ['dog']}

# 중복 제거 + 집합 대수.
print(set([1, 2, 2, 3, 3, 3]))   # {1, 2, 3}
print({1, 2, 3} & {2, 3, 4})     # {2, 3} — 교집합

# two-sum 트릭: 중첩 반복문 O(n^2) 대신 dict 로 O(n).
def two_sum(nums, target):
    seen = {}                              # 값 -> 인덱스
    for i, x in enumerate(nums):
        if target - x in seen:             # 보수를 이미 봤나? O(1)
            return (seen[target - x], i)
        seen[x] = i                        # 이 수를 기억
    return None
print(two_sum([2, 7, 11, 15], 9))          # (0, 1): 2 + 7 = 9, 한 패스에

Exercise

단어 리스트가 주어지고 애너그램을 묶고 싶어 ('eat', 'tea', 'ate' 가 한 그룹). 무차별은 모든 쌍 비교 — O(n² · k). dict 로 O(n · k log k) 해법을 설계하고, 묶기 키로 뭘 쓸지 말해. 키 선택이 왜 모든 애너그램을 일부러 같은 버킷에 충돌하게 해?

Hint

각 단어의 정렬된 글자를 키로 한 defaultdict(list) 를 써: sorted('eat') == sorted('tea') == 'aet'. 모든 애너그램이 동일한 정렬 키를 만들어, 같은 버킷에 해시돼 — 의도적 충돌을 묶기 메커니즘으로.

연산이 다 O(1)

외울 가치 있는 패턴

영원히 값하는 반사신경

피파의 고백

Code

External links

Exercise

Progress

댓글 0