해시(딕셔너리)

🎯 학습 목표

이 강을 마치면 해시 테이블이 어떻게 평균 O(1) 조회를 해내는지 원리로 설명할 수 있습니다. 그리고 파이썬의 딕셔너리와 집합을 상황에 맞게 골라 쓰고, 빈도 세기·중복 판별·짝 찾기 같은 해시로 푸는 대표 문제를 O(n)으로 해결할 수 있게 됩니다.

1강에서 "집합이 리스트보다 훨씬 빠르다"는 결과만 봤습니다. 이번에는 왜 그런지를 들여다봅니다. 원리를 알면 언제 해시가 안 통하는지도 판단할 수 있습니다.

💡 해시 테이블의 원리

해시 테이블의 아이디어는 단순합니다. 값을 보고 저장할 위치를 계산해 버리는 것입니다. 그러면 찾을 때도 같은 계산을 해서 바로 그 자리로 가면 됩니다. 앞에서부터 훑을 필요가 없습니다.

해시 테이블의 동작

  키 "apple" 을 저장하려면

   "apple" ──[해시 함수]──▶ 큰 정수 ──[테이블 크기로 나눈 나머지]──▶ 3번 칸

          0     1     2     3     4     5     6
       ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┐
       │     │     │     │apple│     │     │     │
       └─────┴─────┴─────┴─────┴─────┴─────┴─────┘

  찾을 때도 똑같이 계산 → 3번 칸을 바로 본다  →  O(1)

  ▲ 배열은 '인덱스'를 알아야 O(1)이었다.
    해시는 '값 자체'로 인덱스를 만들어 낸다.

  충돌(collision) — 다른 키가 같은 칸으로 갈 때

   "apple" → 3번
   "grape" → 3번   ← 같은 칸!

  해결 방법 (개념)
   ① 체이닝    : 그 칸에 여러 개를 매달아 두고 순서대로 비교
   ② 개방 주소 : 비어 있는 다음 칸을 찾아 넣는다
   ※ CPython 딕셔너리는 개방 주소 계열 방식을 쓴다.
     세부 구현은 버전에 따라 달라질 수 있다.

  ▲ 충돌이 많아지면 한 칸에 여러 개가 몰려
    비교를 여러 번 하게 된다 → 최악 O(n)
    그래서 '평균 O(1), 최악 O(n)' 이라고 말한다.

실무에서 최악의 경우를 만나기는 어렵습니다. 파이썬은 원소가 늘어나면 테이블을 자동으로 키워 충돌을 낮추기 때문입니다. 그래서 평균 O(1)로 생각하고 쓰면 됩니다.

다만 해시할 수 있는 값만 키가 될 수 있습니다. 값이 변하면 해시값도 변해 위치를 못 찾기 때문에, 파이썬은 수정 불가능한 자료형만 키로 허용합니다.

키로 쓸 수 있는가	자료형	이유
가능	정수, 실수, 문자열, 튜플, frozenset	수정 불가능
불가능	리스트, 딕셔너리, 집합	수정 가능

좌표를 키로 쓰고 싶다면 [1, 2]가 아니라 튜플 (1, 2)를 써야 하는 이유가 이것입니다. 격자 문제에서 자주 쓰는 기법입니다.

📖 딕셔너리와 집합 골라 쓰기

둘 다 해시 테이블 위에 있지만 용도가 다릅니다.

구분	딕셔너리 dict	집합 set
담는 것	키 → 값 쌍	값만
쓰는 때	무언가를 세거나 매핑할 때	있는지 없는지만 볼 때
중복	키는 유일	값이 유일
조회	평균 O(1)	평균 O(1)

실무에서 쓰는 판단 기준은 간단합니다. "값이 필요한가?" 필요하면 딕셔너리, 존재 여부만 알면 되면 집합입니다.

딕셔너리를 편하게 쓰는 도구도 알아 두면 좋습니다.

• d.get(key, 기본값) — 키가 없어도 오류 없이 기본값을 돌려줍니다.
• collections.defaultdict(int) — 없는 키에 접근하면 자동으로 0을 만들어 줍니다. defaultdict(list)면 빈 리스트입니다.
• collections.Counter — 빈도 세기에 특화된 딕셔너리입니다. most_common(k)로 상위 k개를 바로 뽑을 수 있습니다.

집합의 연산도 유용합니다. a & b는 교집합, a | b는 합집합, a - b는 차집합입니다. 두 목록의 공통 원소를 찾는 문제를 한 줄로 풀 수 있습니다.

💻 실전 예제 — 해시로 O(n)에 푸는 문제들

해시가 어떻게 복잡도를 낮추는지 세 가지 문제로 확인하겠습니다.

from collections import Counter, defaultdict


def has_duplicate(nums):
    """중복이 있는지 → O(n)"""
    return len(nums) != len(set(nums))


def two_sum(nums, target):
    """더해서 target 이 되는 두 인덱스 → O(n)"""
    seen = {}                       # 값 → 인덱스
    for i, num in enumerate(nums):
        need = target - num         # 짝이 되려면 필요한 값
        if need in seen:            # 이미 지나온 값 중에 있나? O(1)
            return [seen[need], i]
        seen[num] = i               # 없으면 나를 기록해 둔다
    return []


def group_anagrams(words):
    """같은 글자로 이루어진 단어끼리 묶기"""
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))    # 정렬한 문자열이 같으면 애너그램
        groups[key].append(w)
    return list(groups.values())


print(has_duplicate([1, 2, 3, 2]))              # True
print(two_sum([2, 7, 11, 15], 9))               # [0, 1]
print(group_anagrams(["eat", "tea", "tan", "ate"]))
# [['eat', 'tea', 'ate'], ['tan']]
print(Counter("banana").most_common(2))         # [('a', 3), ('n', 2)]

코드를 줄 단위로 보겠습니다.

• len(nums) != len(set(nums)) — 집합은 중복을 자동으로 제거합니다. 길이가 줄었다면 중복이 있었다는 뜻입니다. 집합 생성이 O(n)이므로 전체 O(n)입니다. 이중 반복문으로 비교하면 O(n²)입니다.
• need = target - num — 두 수를 다 찾으려 하지 않는 것이 핵심입니다. 지금 값이 정해지면 짝은 하나로 결정됩니다.
• if need in seen — 딕셔너리 조회라 평균 O(1)입니다. 이 한 줄이 O(n²) 풀이를 O(n)으로 바꿉니다.
• seen[num] = i — 확인한 뒤에 기록하는 순서가 중요합니다. 먼저 기록하면 같은 원소를 두 번 쓰는 답이 나올 수 있습니다.
• defaultdict(list) — 없는 키에 append를 바로 할 수 있습니다. 일반 딕셔너리면 if key not in d: d[key] = []를 매번 써야 합니다.
• "".join(sorted(w)) — 단어를 정렬한 문자열을 키로 씁니다. "eat"와 "tea"는 둘 다 "aet"가 되어 같은 묶음에 들어갑니다.
• Counter(...).most_common(2) — 가장 많이 나온 2개를 (값, 횟수) 형태로 돌려줍니다. 직접 정렬할 필요가 없습니다.

two_sum은 해시의 전형적인 쓰임을 보여 줍니다. "지나온 것을 기억해 두고, 새 원소를 볼 때마다 필요한 짝이 이미 있는지 O(1)로 확인한다." 이 패턴은 부분합·구간합 문제에도 그대로 쓰입니다.

⚠️ 자주 하는 실수

첫째, 리스트를 키로 쓰려 합니다. d[[1, 2]] = 3은 오류입니다. 튜플 (1, 2)로 바꾸세요. 반대로 튜플 안에 리스트가 들어 있으면 그 튜플도 키가 될 수 없습니다.

둘째, 없는 키에 바로 접근합니다. d[key] += 1은 키가 없으면 오류입니다. d.get(key, 0) + 1이나 defaultdict(int)를 쓰세요.

셋째, 순서를 보장받으려고 딕셔너리를 씁니다. 현재 파이썬 딕셔너리는 삽입 순서를 유지하지만, 이것은 정렬이 아닙니다. 값 순으로 정렬된 결과가 필요하면 sorted()를 명시적으로 써야 합니다.

넷째, 집합에 넣었는데 중복이 안 사라진다고 당황합니다. 집합은 값이 같은지로 판단합니다. 리스트를 담을 수 없으니 튜플로 바꿔 넣어야 좌표 중복 제거가 됩니다.

다섯째, 해시가 항상 답이라고 생각합니다. 해시는 순서를 잃습니다. "정렬된 상태에서 가장 가까운 값" 같은 문제는 해시로 풀 수 없고 이분 탐색(10강)이 맞습니다. 또 메모리를 O(n) 더 쓰므로, 메모리 제한이 빡빡하면 다른 접근이 필요합니다.

📝 핵심 요약 + 다음 강 예고

이번 강의 내용을 정리합니다.

#	기억할 것
1	해시는 값으로 위치를 계산해 바로 찾아간다
2	그래서 평균 O(1), 최악 O(n)
3	키는 수정 불가능한 자료형만 (리스트 ✕, 튜플 ○)
4	값이 필요하면 dict, 존재 여부만이면 set
5	defaultdict·Counter로 코드가 크게 줄어든다
6	"지나온 것을 기억"하는 패턴이 O(n²)를 O(n)으로
7	해시는 순서를 잃는다 — 정렬이 필요하면 다른 도구

지금 해 볼 것은 two_sum을 이중 반복문으로도 짜 보고 n을 10,000쯤으로 키워 시간을 비교하는 것입니다. O(n²)와 O(n)의 차이를 직접 확인할 수 있습니다.

다음 8강 「정렬 기초」에서는 정렬로 넘어갑니다. 버블·선택·삽입 정렬이 왜 O(n²)인지 원리로 이해하고, 파이썬의 sort()가 무엇을 대신해 주는지, 그리고 key 인자로 정렬 기준을 바꾸는 법을 다루겠습니다.

📚 참고 자료

• Dictionaries — Python 공식 문서
• collections.defaultdict — Python 공식 문서
• Set Types — Python 공식 문서
• TimeComplexity — Python Wiki