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 차집합)도 두 집합 크기의 곱이 아니라 크기에 비례하는 시간에 끝나. 이게 기본 재료고, 남은 건 언제 꺼내 쓸지 아는 감각이야.

외울 가치가 있는 패턴

중복 제거는 set(items). 고유한 원소만 즉시 남아.
멤버십은 x in some_list 대신 x in some_set. O(n)과 O(1)의 차이고, 가장 흔한 속도 개선이야.
세기는 collections.Counter(items). 한 번 훑고 모든 원소의 빈도를 얻어.
묶기는 collections.defaultdict(list). '이 키가 이미 있나?'를 확인하지 않고 키별로 담을 수 있어.
캐싱과 메모이제이션은 입력을 계산 결과에 대응시키는 dict. 동적 계획법 트랙의 심장이 이거야.
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