B-3: 해시 테이블 — "값 자체로 위치를 계산해 평균 O(1)에 찾는다"

안녕하세요! 코딩테스트와 CS의 길잡이, 홍순구 튜터입니다.

지난 시간엔 노드와 포인터로 연결 리스트를 직접 이었습니다. 단일·이중 리스트를 잇고, 더미 헤드로 경계 예외를 지우고, 토끼와 거북이로 고리까지 잡았죠. 그러면서 한 가지 답답함을 마지막에 남겨 뒀습니다. "값으로 원소를 찾기"는 늘 O(n)이라는 것이었어요.

생각해 보면 지금까지 배운 그릇이 전부 그랬습니다. 배열도, 연결 리스트도, 스택·큐도, "값 7이 어디 있지?"를 알려면 처음부터 하나씩 비교해야 했어요. 원소가 10만 개면 최악엔 10만 번을 봐야 합니다.

오늘은 그 벽을 깹니다. 값을 보고 "몇 번 칸에 있는지"를 곧장 계산해서, 그 칸으로 바로 가는 그릇 — 해시 테이블(hash table)입니다. 평균적으로 넣기·찾기·지우기가 모두 O(1)이에요. 파이썬의 dict와 set이 바로 이것입니다. 마법처럼 보이지만, 비밀은 딱 두 가지(해시 함수와 충돌 처리)뿐이라 오늘 직접 짜 보면 또렷해집니다.

 오늘의 여정 — "값 자체로 위치를 계산해 평균 O(1)에 찾는다"

 [1] 왜 해시인가      →  값으로 찾기 O(n)의 벽, 값을 칸 번호로 쓰는 발상
 [2] 해시 함수        →  임의의 키를 0..N-1 칸 번호로 압축 (% 연산)
 [3] 충돌과 체이닝     →  같은 칸에 몰리면? 리스트로 매단다 (연결 리스트 재등장)
 [4] 개방 주소법       →  차 있으면 옆 칸으로, 삭제의 무덤(tombstone) 함정
 [5] 적재율과 리사이징  →  왜 평균 O(1)인가, 빽빽해지면 칸을 늘린다
 [6] dict·set 활용     →  실전 코테의 무기, 두 수의 합 O(n²)→O(n)
 [7] 카운팅           →  Counter로 빈도수 한 줄에

자, 값을 곧장 찾는 마법 같은 그릇을 만들러 가 봅시다. 출발합니다!

💡 오늘 수업의 핵심 — "해시 함수로 값을 칸 번호로 바꿔 평균 O(1)에 넣고 찾는 원리를 직접 구현하고, 충돌을 체이닝·개방 주소법으로 푸는 두 방법을 손으로 짜며, 실전에선 dict·set·Counter로 O(1) 조회를 무기처럼 쓴다"

🎯 학습 목표

• 해시 함수(키 → 칸 번호)와 충돌 처리(체이닝·개방 주소법)를 직접 구현하고, 삽입·조회·삭제의 평균 O(1)·최악 O(n)을 빅오로 짚습니다.
• 적재율(load factor)과 리사이징으로 "왜 평균 O(1)이 유지되는가, 언제 최악 O(n)으로 무너지는가"를 이해합니다.
• 실전 코테에서 dict·set·Counter로 O(1) 조회와 빈도수 세기를 활용해, O(n²) 완전탐색을 O(n)으로 끌어내립니다.

Step 1: "값으로 찾기 O(n)의 벽" — 왜 해시인가

지난 시간 마무리에서 던진 질문부터 다시 봅시다. 값으로 원소를 찾으려면 왜 늘 O(n)이었을까요? 배열이든 연결 리스트든, 원소가 "어디 있는지"를 미리 알 길이 없어 처음부터 하나씩 비교했기 때문입니다. 값과 위치 사이에 아무 약속이 없었던 거죠.

해시는 발상을 뒤집습니다. 값 자체로 위치를 계산하기로 약속하는 거예요. 사물함을 떠올려 보세요. 이름표를 보고 "김씨는 1번 칸, 이씨는 2번 칸"처럼 칸 번호를 곧장 계산할 수 있다면, 찾을 때 모든 칸을 열어 볼 필요 없이 계산한 그 칸으로 바로 갑니다.

가장 단순한 형태가 직접 주소법(direct addressing)입니다. 키가 0~9 정수라면, 크기 10짜리 배열을 만들고 arr[키]로 곧장 넣고 찾으면 O(1)이에요. 사실 지난 A-2에서 알파벳을 26칸 배열로 세던 게(char_count) 바로 이 직접 주소법이었습니다.

그런데 키가 정수가 아니거나(이메일·이름) 범위가 거대하면(전화번호) 문제가 생깁니다. 전화번호를 직접 주소로 쓰려면 칸이 천문학적으로 필요해 메모리가 터져요. 그래서 해시 함수로 "큰 키를 작은 칸 번호로 압축"합니다. 이게 해시 테이블의 출발점이에요.

 직접 주소법 — 키를 칸 번호로 그대로 쓴다
   키 0~9 정수   →  크기 10 배열, arr[키] 로 곧장 O(1)
   키가 전화번호 "010-1234-5678" 이라면?  →  칸이 천문학적으로 필요 (낭비)

 해싱 — 큰 키를 작은 칸 번호로 압축한다
   임의의 키  ─(해시 함수)─▶  0..N-1 칸 번호  ─▶  그 칸으로 곧장 O(1)

🎯 코테에서는 해시가 "이 값 봤었나?", "몇 번 나왔나?", "짝이 되는 값이 있나?"를 평균 O(1)에 답하는 만능 도구입니다. 시간 초과로 막힌 완전탐색 풀이를, "해시로 기록해 두고 O(1)에 조회"로 바꿔 통과시키는 게 코테의 단골 전략이에요.

💡 한 줄 정리

해시 테이블은 값 자체로 칸 번호를 계산해 그 칸으로 곧장 가는 그릇이다. 키가 작은 정수면 직접 주소법(arr[키])으로 충분하지만, 키가 크거나 정수가 아니면 해시 함수로 작은 칸 번호로 압축한다.

Step 2: "값을 칸 번호로 압축한다" — 해시 함수

해시 함수(hash function)는 임의의 키를 0..capacity-1 범위의 정수(칸 번호)로 바꾸는 함수입니다. 핵심 도구는 의외로 단순해요. 바로 나머지 연산(%)입니다. 칸이 8개라면 어떤 정수든 % 8을 하면 0~7 사이로 가둬지죠.

정수 키는 key % capacity 한 방이면 됩니다. 그럼 문자열은요? 글자들을 숫자로 바꿔 섞어야 합니다. A-2에서 글자를 아스키 코드로 바꾸던 ord를 다시 꺼냅니다. 각 글자의 ord 값을 위치마다 섞어 가며 누적해 큰 정수를 만들고, 마지막에 % capacity로 칸 번호 범위에 가두는 거예요.

# structures/hash_table.py

def string_hash(text, capacity):
    """문자열을 0..capacity-1 범위의 인덱스로 바꾸는 해시 함수. 시간 O(len(text)).

    각 글자의 아스키 코드(ord)를 자리값과 함께 누적해 골고루 섞은 뒤(다항식 해싱),
    capacity로 나눈 나머지(%)를 취해 칸 번호 범위 안에 가둔다. 같은 문자열은 늘
    같은 값이 나오고(결정성), 서로 다른 문자열은 되도록 다른 칸으로 흩어진다.
    """
    h = 0
    for ch in text:
        h = h * 31 + ord(ch)        # 31: 자리마다 섞어 충돌을 줄이는 흔한 상수
    return h % capacity             # %로 0..capacity-1 범위에 가둔다

 해시 함수 — "apple" 을 칸 번호로 (capacity=8)

  'a'   'p'   'p'   'l'   'e'
   │     │     │     │     │    각 글자 ord 를 h = h*31 + ord 로 누적
   └─────┴─────┴─────┴─────┘    →  큰 정수 h
                       h % 8    →  0..7 중 한 칸 번호

좋은 해시 함수는 두 성질을 가집니다. 첫째 결정성 — 같은 키를 넣으면 늘 같은 칸이 나와야 다음에 그 칸에서 찾을 수 있어요. 둘째 균등 분포 — 서로 다른 키들이 되도록 여러 칸에 고루 흩어져야 한 칸에 몰리지 않습니다. string_hash("apple", 8)은 몇 번을 호출해도 같은 값이 나오고, 0~7 범위를 벗어나지 않습니다.

빅오로 보면, 칸 번호를 계산하는 일 자체는 정수 키면 O(1), 문자열 키면 글자 수에 비례해 O(len)입니다. 보통 키 길이는 짧고 일정해서 사실상 상수로 취급해요. 이 "한 번의 계산으로 위치가 정해진다"가 평균 O(1)의 첫 비밀입니다.

🎯 코테에서는 파이썬의 dict·set이 내부적으로 이 해시 함수(내장 hash())를 씁니다. 직접 짤 일은 거의 없지만, "해시가 왜 빠른가요?"라는 면접 질문의 답이 바로 여기 있어요. "키를 한 번 계산해 칸 번호를 정하니, 모든 칸을 뒤지지 않고 곧장 그 칸으로 간다"가 핵심 멘트입니다.

💡 한 줄 정리

해시 함수는 임의의 키를 % capacity로 0..capacity-1 칸 번호에 가둔다. 같은 키는 늘 같은 칸(결정성), 다른 키는 고루 흩어지게(균등 분포) 만드는 게 목표다. 문자열은 글자 ord를 섞어 큰 정수로 만든 뒤 압축한다.

Step 3: "같은 칸에 몰리면 리스트로 매단다" — 충돌과 체이닝

해시 함수는 큰 키 공간을 작은 칸으로 압축합니다. 그러면 피할 수 없는 일이 생겨요. 서로 다른 두 키가 같은 칸 번호로 떨어지는 겁니다. 이걸 충돌(collision)이라고 합니다.

충돌은 운이 나빠서가 아니라 반드시 일어납니다. 비둘기집 원리(pigeonhole principle) — 비둘기가 집보다 많으면 한 집에 둘 이상이 들어갈 수밖에 없죠. 키는 무한히 많고 칸은 유한하니, 충돌은 수학적으로 불가피해요. 그래서 해시 테이블의 절반은 "충돌을 어떻게 푸느냐"입니다.

첫 번째 해법이 체이닝(chaining, 분리 연결법)입니다. 한 칸에 하나만 담는 대신, 그 칸에 (키, 값) 쌍을 리스트로 줄줄이 매다는 거예요. 지난 시간에 노드를 이어 만든 연결 리스트가 바로 여기서 다시 등장합니다. 같은 칸으로 충돌한 쌍들을 한 줄로 잇는 거죠. 조회할 때는 그 칸의 짧은 리스트만 훑으면 됩니다.

# structures/hash_table.py

class HashTableChaining:

    def __init__(self, capacity=8):
        self._capacity = capacity
        self._size = 0
        self._buckets = [[] for _ in range(capacity)]   # 각 칸 = (키,값) 쌍의 리스트

    def _index(self, key):
        """키를 칸 번호로. 파이썬 내장 hash()를 capacity로 압축. 평균 O(1)."""
        return hash(key) % self._capacity

    def put(self, key, value):
        """키-값을 넣는다(있으면 갱신). 평균 O(1). 적재율 0.75 초과 시 리사이징."""
        bucket = self._buckets[self._index(key)]
        for pair in bucket:                 # 같은 칸의 체인을 훑어 기존 키면 갱신
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])         # 없으면 체인 끝에 새 쌍을 잇는다
        self._size += 1
        if self._size > self._capacity * 0.75:    # 너무 빽빽해지면 칸을 늘려 흩는다
            self._resize(self._capacity * 2)

put을 보세요. 먼저 _index로 칸 번호를 계산하고, 그 칸의 리스트(체인)를 훑습니다. 같은 키가 이미 있으면 값만 갱신하고, 없으면 끝에 새 쌍을 이어 붙여요. 조회하는 get도 똑같이 그 칸의 리스트만 훑습니다.

    def get(self, key):
        """키로 값을 찾는다(없으면 KeyError). 평균 O(1) — 한 칸의 짧은 체인만 훑는다."""
        for pair in self._buckets[self._index(key)]:
            if pair[0] == key:
                return pair[1]
        raise KeyError(key)

 체이닝 — 같은 칸으로 충돌하면 리스트로 매단다 (capacity=4)

  칸0: [ ]
  칸1: [ (1,"a") ]─[ (5,"b") ]   ← 1%4 == 5%4 == 1, 같은 칸에 줄줄이 잇는다
  칸2: [ ]
  칸3: [ (7,"c") ]

  조회: 그 칸의 짧은 리스트만 훑어 키를 찾는다

여기서 빅오가 갈립니다. 키들이 칸에 고루 흩어지면 한 칸의 체인 길이가 평균 1 근처라 조회·삽입·삭제가 모두 평균 O(1)이에요. 반대로 (해시 함수가 나쁘거나 운이 나빠) 모든 키가 한 칸에 몰리면 그 칸의 체인이 길이 n이 되어, 결국 그 리스트를 처음부터 훑는 최악 O(n)이 됩니다. 그래서 "평균 O(1), 최악 O(n)"이라고 늘 함께 적어요.

🎯 코테에서는 충돌을 직접 처리할 일은 없지만, "해시가 평균 O(1)인데 왜 최악 O(n)이냐"는 면접 단골 질문의 답이 여기 있습니다. "모든 키가 한 칸으로 충돌하면 그 칸의 체인이 선형 탐색이 되기 때문"이라고 답하면 원리를 아는 사람으로 보여요.

💡 한 줄 정리

충돌은 비둘기집 원리로 피할 수 없다. 체이닝은 같은 칸에 (키,값) 쌍을 리스트로 매달아(연결 리스트처럼) 푼다. 고루 흩어지면 평균 O(1), 한 칸에 몰리면 그 체인을 훑어 최악 O(n)이다.

Step 4: "차 있으면 옆 칸으로" — 개방 주소법과 무덤

충돌을 푸는 두 번째 방법은 발상이 다릅니다. 체인을 매달지 않고, 칸이 차 있으면 바로 다음 빈 칸으로 옮겨 넣는 거예요. 이걸 개방 주소법(open addressing), 그중에서도 한 칸씩 옆으로 가는 방식을 선형 탐사(linear probing)라고 합니다. 모든 (키,값)이 배열 한 칸씩에 직접 살아요.

조회도 같은 순서로 합니다. 계산한 칸부터 옆으로 훑다가, 키를 만나면 반환하고, 빈 칸(None)을 만나면 "없음"이에요(거기까지 갔는데 없으면 더 갈 이유가 없으니까).

# structures/hash_table.py

class HashTableOpenAddressing:

    _EMPTY = None
    _DELETED = object()     # tombstone: '여기 있었지만 지워졌다'는 표식

    def __init__(self, capacity=8):
        self._capacity = capacity
        self._size = 0          # 살아있는 (키,값) 수
        self._used = 0          # 빈칸이 아닌 칸 수(살아있는 것 + 무덤)
        self._slots = [self._EMPTY] * capacity   # 각 칸: None / _DELETED / [키,값]

    def get(self, key):
        """키로 값을 찾는다. 탐사 순서대로 훑다 빈 칸(None) 만나면 없음. 평균 O(1)."""
        idx = self._index(key)
        while self._slots[idx] is not self._EMPTY:
            slot = self._slots[idx]
            if slot is not self._DELETED and slot[0] == key:
                return slot[1]
            idx = (idx + 1) % self._capacity
        raise KeyError(key)

get에서 idx = (idx + 1) % self._capacity가 "옆 칸으로 한 칸 이동"입니다(끝에 닿으면 %로 다시 0번 칸으로 순환해요). 빈 칸을 만날 때까지 옆으로 훑는 거죠.

이 방식의 진짜 함정은 삭제입니다. 칸을 그냥 None으로 비우면 큰일 나요. 그 칸을 건너뛰며 옆 칸에 넣어 뒀던 뒤 키들의 탐사 경로가 끊겨, 멀쩡히 있는 값을 못 찾게 됩니다. 그래서 삭제할 때는 빈 칸으로 만들지 않고 '삭제됨' 표식(tombstone, 무덤)을 남깁니다. 조회는 무덤을 "건너뛰되 멈추지는 않고" 계속 옆으로 갑니다.

    def remove(self, key):
        """키를 찾아 tombstone으로 표시(빈칸 None으로 두지 않는다). 평균 O(1)."""
        idx = self._index(key)
        while self._slots[idx] is not self._EMPTY:
            slot = self._slots[idx]
            if slot is not self._DELETED and slot[0] == key:
                self._slots[idx] = self._DELETED    # 경로를 끊지 않도록 무덤 표식
                self._size -= 1
                return
            idx = (idx + 1) % self._capacity
        raise KeyError(key)

 개방 주소법(선형 탐사) — 차 있으면 옆 칸으로 (capacity=8)

  put(1,"a")  →  칸1 비었음, 넣는다            칸1:(1,"a")
  put(9,"b")  →  9%8==1, 칸1 찼음 → 옆 칸2로   칸2:(9,"b")

 ⚠️ 삭제의 함정 — 칸1 을 그냥 None 으로 비우면 9 를 못 찾는다

  remove(1) 을 None 으로:     칸1:None    칸2:(9,"b")
    get(9): 9%8==1 → 칸1 이 빈칸 → "없음"으로 잘못 멈춤 ❌

  remove(1) 을 무덤(DELETED)으로:  칸1:DELETED  칸2:(9,"b")
    get(9): 칸1 은 무덤이라 건너뜀 → 칸2 에서 9 발견 ✅

두 방법을 비교하면 이렇습니다.

🎯 코테에서는 파이썬의 dict가 개방 주소법(에 가까운) 방식을 씁니다. 둘을 직접 짤 일은 드물지만, "체이닝과 개방 주소법의 차이는?"이라고 물으면 위 표가 답이에요. "체이닝은 칸 밖 리스트로 풀고, 개방 주소법은 배열 안에서 옆 칸으로 풀되 삭제 시 무덤이 필요하다"가 핵심 멘트입니다.

💡 한 줄 정리

개방 주소법은 충돌하면 옆 빈 칸으로 옮겨 넣고(선형 탐사), 조회도 옆으로 훑다 빈 칸 만나면 멈춘다. 삭제 시 칸을 None으로 비우면 탐사 경로가 끊기므로, 무덤(tombstone) 표식을 남겨 경로를 잇는다.

Step 5: "왜 평균 O(1)인가" — 적재율과 리사이징

지금까지 "평균 O(1)"을 당연한 듯 써 왔는데, 그게 공짜로 유지되는 건 아닙니다. 비결은 적재율(load factor)이에요. 적재율은 간단합니다.

 적재율(load factor) = 원소 수 / 칸 수

  칸 4개에 원소 3개  →  적재율 0.75,  한 칸에 둘 이상 몰리기 시작
       ▼  리사이징: 칸을 8개로 늘리고 전부 다시 흩는다(rehash)
  칸 8개에 원소 3개  →  적재율 0.375,  다시 넉넉 → 평균 O(1) 유지

적재율이 낮으면(칸에 비해 원소가 적으면) 충돌이 드물어 한 칸에 거의 하나씩 들어가 평균 O(1)입니다. 적재율이 높아지면(빽빽해지면) 충돌이 잦아져 체인이 길어지거나 탐사가 길어져 O(n) 쪽으로 다가가요. 그래서 적재율이 임계값(체이닝은 보통 0.75, 개방 주소법은 0.5)을 넘으면 칸을 두 배로 늘리고 모든 원소를 새 위치로 다시 흩습니다. 이게 리사이징(resizing), 다시 흩는 일을 재해싱(rehash)이라고 해요.

# structures/hash_table.py (HashTableChaining)

    def _resize(self, new_capacity):
        """칸 수를 늘리고 모든 쌍을 새 칸 위치로 다시 흩는다(rehash). O(n)."""
        old_pairs = [pair for bucket in self._buckets for pair in bucket]
        self._capacity = new_capacity
        self._buckets = [[] for _ in range(new_capacity)]
        self._size = 0
        for key, value in old_pairs:
            self.put(key, value)

칸 수가 바뀌면 _index의 % capacity 결과도 바뀌니, 모든 쌍을 새 칸으로 다시 넣어야 합니다(그래서 옛 쌍을 모아 put을 다시 호출해요). 한 번 리사이징은 모든 원소를 옮기니 O(n)입니다.

"리사이징이 O(n)이면 그때마다 느려지는 거 아닌가?" 싶죠. 여기서 A-1·B-1에서 본 분할상환(amortized)이 다시 나옵니다. 칸을 두 배씩 늘리면 리사이징은 아주 가끔만 일어나고(원소가 두 배가 될 때마다 한 번), 그 비용을 그동안의 수많은 O(1) 삽입에 나눠 펴면 삽입 한 번당 평균 O(1)이 됩니다. 파이썬 리스트의 append가 가끔 내부 배열을 키우면서도 평균 O(1)인 것과 똑같은 원리예요.

빅오로 정리하면, 적재율을 낮게 유지하는 한 해시 테이블은 평균 O(1)입니다. "1초에 약 1억 연산" 잣대로 보면, 원소 10만 개를 평균 O(1)로 조회하면 10만 번 계산이라 순식간이에요. 만약 적재율 관리에 실패해 다 한 칸에 몰리면(최악 O(n)) 10만 곱하기 10만 = 100억이 되어 시간 초과로 떨어집니다. 적재율 관리가 평균 O(1)을 지키는 마지막 열쇠인 이유예요.

🎯 코테에서는 리사이징을 직접 구현할 일은 없습니다(dict·set이 알아서 해요). 다만 "해시가 평균 O(1)인데 왜 최악 O(n)?"이라는 질문에 "충돌이 한 칸에 몰리거나 적재율이 높을 때. 그래서 리사이징으로 적재율을 낮게 유지한다"까지 답하면 원리를 정확히 아는 사람으로 보입니다.

💡 한 줄 정리

적재율 = 원소 수 / 칸 수. 낮으면 충돌이 드물어 평균 O(1), 높으면 O(n)으로 무너진다. 임계를 넘으면 칸을 두 배로 늘려 다시 흩는다(리사이징, O(n))는데, 두 배씩 키우면 분할상환으로 삽입당 평균 O(1)이 지켜진다.

Step 6: "실전 코테의 무기" — dict·set 전략적 활용

여기까지 해시를 손으로 짠 건 원리를 보기 위함이었습니다. 실전 코테에선 이걸 직접 짜지 않아요. 파이썬의 dict와 set을 그냥 씁니다. C로 구현돼 우리 코드보다 빠르고 버그도 없거든요. 직접 구현으로 원리를 봤으니, 이제 내장 도구를 무기로 쓰는 트랙입니다.

핵심은 단 하나, in 조회의 빅오가 자료구조마다 다르다는 거예요. 리스트에 x in nums를 하면 처음부터 훑어 O(n)이지만, set이나 dict에 x in s를 하면 해시로 곧장 찾아 평균 O(1)입니다. 이 차이 하나가 코테의 당락을 가릅니다.

대표 예가 두 수의 합(two sum)입니다. "배열에서 합이 target인 두 수의 인덱스를 찾아라." 이중 for로 모든 쌍을 보면 O(n²)이에요. 대신 "지금까지 본 수 → 인덱스"를 dict에 기록해 두고, 각 수마다 보수(target - 그 수)가 이미 있는지 O(1)에 조회하면 한 번의 순회로 끝납니다.

# structures/hash_table.py

def two_sum(nums, target):
    """합이 target인 두 수의 '인덱스 쌍'을 찾는다(없으면 None). 시간 O(n)·공간 O(n).

    이중 for로 모든 쌍을 보면 O(n^2)다. 대신 '지금까지 본 수 → 인덱스'를 dict에
    기록해 두고, 각 수마다 target - 그 수(보수)를 dict에서 O(1)에 찾으면 한 번의
    순회로 끝난다. 해시의 평균 O(1) 조회가 O(n^2)를 O(n)으로 끌어내린다.
    """
    seen = {}                       # 값 -> 인덱스
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:            # 보수를 이미 봤다면 평균 O(1)에 찾음
            return (seen[need], i)
        seen[x] = i
    return None

 두 수의 합 — target=9,  nums=[2, 7, 11, 15]

  i=0  x=2   보수 7   seen={}       7 없음  → seen={2:0}
  i=1  x=7   보수 2   seen={2:0}    2 있음! → (0, 1) 반환

  한 번 순회 O(n)   (이중 for 였다면 O(n²))

two_sum([2, 7, 11, 15], 9)를 넣으면 (0, 1)이 나옵니다(2 + 7 = 9). 빅오가 O(n²)에서 O(n)으로 내려간 게 핵심이에요. "1초에 1억 연산" 잣대로, 원소가 10만 개라면 O(n²)은 100억이라 시간 초과지만 O(n)은 10만이라 넉넉히 통과합니다.

set도 같은 무기예요. 값까지는 필요 없고 "있나 없나"만 따질 때 씁니다. 예를 들어 "배열에 중복이 있나?"는 len(set(nums)) != len(nums) 한 줄로 평균 O(n)에 끝나죠.

🎯 코테에서는 "리스트에 in으로 찾으면 O(n), set/dict로 바꾸면 O(1)" — 이 치환 하나로 시간 초과가 통과로 바뀝니다. 완전탐색으로 짠 풀이가 시간을 넘기면, 가장 먼저 "조회를 해시로 바꿀 수 있나?"를 떠올리세요. 두 수의 합, 중복 검사, 부분합 존재 여부가 전부 이 패턴이에요.

💡 한 줄 정리

실전에선 직접 구현 대신 dict·set을 쓴다. 리스트 in은 O(n)이지만 set·dict in은 평균 O(1) — 이 차이로 O(n²) 완전탐색을 O(n)으로 끌어내린다. 값이 필요하면 dict, 존재 여부만이면 set이다.

Step 7: "빈도수를 한 줄에" — Counter와 카운팅

해시의 가장 흔한 쓰임이 빈도수 세기(counting)입니다. "어떤 값이 몇 번 나왔나"를 세는 거죠. A-2에서 알파벳을 26칸 배열로 셌던 걸 기억하시죠? 그건 키가 알파벳 26개로 정해진 특수한 경우였어요. 키가 무엇이든(단어, 숫자, 무엇이든) 받으려면 dict로 일반화합니다.

# structures/hash_table.py

def char_frequency(text):
    """글자별 등장 횟수를 dict로 센다. 시간 O(n)·공간 O(서로 다른 글자 수).

    A-2에서 26칸 배열로 알파벳을 세던 것을, 키가 무엇이든 받는 dict로 일반화한다.
    dict.get(ch, 0)으로 '처음 보는 글자면 0부터' 시작해 1씩 더한다.
    """
    freq = {}
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1
    return freq

freq.get(ch, 0)이 핵심이에요. 처음 보는 글자면 0부터 시작하고, 이미 있으면 그 값에 1을 더합니다. char_frequency("banana")를 넣으면 {'b': 1, 'a': 3, 'n': 2}가 나와요. 한 번 훑으니 O(n)입니다.

그런데 이 패턴이 워낙 흔해서, 파이썬이 아예 전용 도구를 줍니다. collections.Counter예요. 위 char_frequency가 통째로 한 줄이 됩니다.

from collections import Counter

Counter("banana")               # Counter({'a': 3, 'n': 2, 'b': 1})
Counter("banana").most_common(1)    # [('a', 3)]  — 가장 많은 1개

Counter는 내부가 dict라 동작도 빅오도 같습니다(O(n) 한 번 훑기). 다만 most_common(최빈값), 두 Counter의 뺄셈 같은 편의 기능을 얹어 줘서 코테에서 손이 빠르게 나가요.

🎯 코테에서는 "완주하지 못한 선수", "빈도수 세기", "애너그램 판정"이 전부 이 카운팅 패턴입니다. A-2에서 애너그램을 정렬로 풀었는데, Counter(s1) == Counter(s2) 한 줄로도 판정돼요(글자 빈도가 같으면 애너그램). most_common으로 최빈값을 뽑는 것까지 함께 익혀 두면 좋습니다.

💡 한 줄 정리

빈도수 세기는 해시의 가장 흔한 쓰임이다. dict.get(키, 0) + 1로 세거나, 더 짧게 collections.Counter로 한 줄에 센다(둘 다 O(n)). most_common으로 최빈값을, Counter 비교로 애너그램을 판정한다.

마무리

오늘은 값 자체로 위치를 계산하는 그릇, 해시 테이블을 만들었습니다. 해시 함수로 키를 칸 번호로 압축하고, 충돌을 체이닝(같은 칸에 리스트로 매달기)과 개방 주소법(옆 빈 칸으로)으로 풀었어요. 적재율을 낮게 유지하려 리사이징까지 보고 나서, 실전에선 dict·set·Counter로 O(1) 조회를 무기처럼 쓰는 데까지 왔습니다. 지난 시간 흘려 둔 "값으로 찾기 O(n)"의 벽이, 오늘 평균 O(1)로 깨졌죠.

오늘 배운 핵심 세 가지

• 💡 하나 — 해시는 값 자체로 칸 번호를 계산해 평균 O(1)에 넣고 찾는다. 비결은 해시 함수(키 → 칸 번호로 압축)와, 같은 칸으로 몰리는 충돌을 푸는 처리다. "값과 위치 사이에 계산 가능한 약속을 둔다"가 O(n) 탐색을 O(1)로 바꾼 발상이다.
• 💡 둘 — 충돌은 비둘기집 원리로 피할 수 없고, 두 방법으로 푼다. 체이닝(같은 칸에 리스트로 매달기)과 개방 주소법(옆 칸으로 옮기되 삭제 시 무덤 표식). 적재율을 낮게 유지(리사이징)해야 평균 O(1)이 지켜지고, 빽빽하거나 한 칸에 몰리면 최악 O(n)이다.
• 💡 셋 — 실전 코테의 무기는 dict·set·Counter다. 리스트 in(O(n))을 set·dict in(평균 O(1))으로 바꿔, O(n²) 완전탐색을 O(n)으로 끌어내린다. 빈도수는 Counter로 한 줄에 센다. 직접 구현으로 원리를 알아야 이 도구를 언제 믿을지 판단한다.

다음 시간 예고

이걸로 카테고리 B, 선형 자료구조가 끝났습니다. 스택·큐·연결 리스트·해시 — 모양은 달라도 전부 데이터를 한 줄로 늘어놓는 그릇이었어요. 원소를 쌓거나, 줄 세우거나, 이어 붙이거나, 칸에 흩어 두거나.

다음 시간(C-1)부턴 데이터가 한 줄이 아니라 가지를 치는 비선형 구조로 넘어갑니다. 첫 주자는 트리(tree)예요. 연결 리스트의 노드가 "다음 하나"를 가리켰다면, 트리의 노드는 "자식 여럿"을 가리킵니다. 가계도처럼 위에서 아래로 갈라지는 구조죠. 오늘 잡은 노드와 포인터 감각이 그대로 이어지니, 한 칸이 여러 칸을 가리키는 그림을 떠올려 두세요. 참고로 오늘 본 해시는 데이터베이스 인덱스의 토대이기도 한데, 그 자료구조를 "언제 어떻게 인덱스로 거나"는 데이터베이스 과목에서 따로 만납니다.

과제

오늘 배운 해시를 직접 손으로 다뤄 보는 문제들입니다. 풀어 본 뒤 예시 답안과 맞춰 보세요. 각 풀이의 시간·공간 복잡도를 빅오로 적는 것도 잊지 마세요.

[기초] 완주하지 못한 선수

마라톤에 참여한 선수들의 이름 리스트 participant와, 완주한 선수들의 이름 리스트 completion이 주어집니다. completion은 participant에서 딱 한 명만 빠진 리스트예요. 완주하지 못한 그 한 명의 이름을 돌려주는 함수를 작성하세요(예: participant=["leo","kiki","eden"], completion=["eden","kiki"] → "leo").

주의할 점이 하나 있습니다. 동명이인이 있을 수 있어요(같은 이름이 둘). 그래서 단순히 두 집합의 차집합(set)으로 풀면 동명이인을 놓칩니다. 빈도수까지 따지는 도구가 무엇일지 떠올려 보세요. 시간·공간 복잡도도 빅오로 적으세요. (프로그래머스 Lv1 빈출 유형입니다.)

[응용] 두 배열의 공통 원소

두 정수 배열 a, b가 주어질 때, 두 배열에 공통으로 등장하는 원소들을 (중복 없이) 돌려주는 함수를 작성하세요(예: a=[1,2,2,3], b=[2,3,4] → {2, 3}). 이중 for로 모든 쌍을 비교하면 a의 길이 n, b의 길이 m에 대해 O(n×m)입니다. 한쪽을 set으로 만들어 in 조회를 O(1)로 바꾸면 전체를 O(n+m)으로 풀 수 있어요. 두 풀이의 빅오를 각각 적고, n과 m이 각각 10만일 때 어느 쪽이 시간 안에 드는지 "1초 1억 연산" 잣대로 한 줄 적으세요.

[심화] 애너그램 그룹 짓기

문자열 리스트가 주어질 때, 서로 애너그램인 것끼리 묶어 그룹들의 리스트로 돌려주는 함수를 작성하세요(애너그램 = 글자 구성이 같고 순서만 다른 단어). 예: ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"], ["tan","nat"], ["bat"]].

A-2에서 두 단어가 애너그램인지 판정할 때 "정렬하면 같아진다"를 봤죠. 여기선 그걸 한 단계 밀고 갑니다. 각 단어를 정렬한 문자열을 키로 삼아 dict에 모으면, 같은 키로 애너그램들이 한 그룹으로 모입니다(예: "eat"·"tea"·"ate"는 정렬하면 모두 "aet"). dict의 값을 리스트로 둬서 같은 키에 단어를 쌓아 보세요. 단어 수 n, 단어 최대 길이 k일 때 시간 복잡도를 빅오로 적으세요. (LeetCode Medium "Group Anagrams" 패턴.)

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. 해시는 평균 O(1)인데, 왜 "최악 O(n)"이라고 늘 함께 적을까?

해시 테이블은 보통 평균 O(1)로 동작하지만, 자료구조 책과 면접관은 꼭 "최악 O(n)"을 함께 묻습니다. 어떤 상황에서 해시가 O(n)으로 무너질까요? 모든 키가 한 칸으로 충돌하는 경우, 적재율이 너무 높은 경우를 떠올려 보세요. 더 나아가, 누군가 일부러 같은 칸으로 몰리는 키들을 입력해 서버를 느리게 만드는 공격(해시 충돌 공격)도 가능합니다. "평균은 빠르지만 최악을 보장하지 못한다"가 해시의 본질적 약점인데, 이걸 어떻게 완화할 수 있을지(좋은 해시 함수, 리사이징, 최악을 O(log n)으로 막는 트리 전환) 생각해 보세요.

2. 체이닝과 개방 주소법, 무엇을 언제 쓸까?

같은 충돌을 푸는 두 방법인데 성격이 다릅니다. 체이닝은 칸 밖에 리스트를 매달아 적재율이 1을 넘어도 동작하지만, 칸마다 리스트(포인터)라는 추가 공간을 씁니다. 개방 주소법은 배열 한 장으로 끝나 메모리가 조밀하고 캐시에 유리하지만, 적재율을 1 미만으로 유지해야 하고 삭제 시 무덤 관리가 필요해요. "메모리를 아끼고 캐시 효율이 중요한 상황"과 "삭제가 잦고 적재율 예측이 어려운 상황" 중 각각 어느 쪽이 어울릴지, 둘의 트레이드오프를 빅오와 공간 관점에서 정리해 보세요.

3. 해시를 직접 짜 봤지만 실전에선 dict를 쓴다 — 그럼 왜 직접 짰을까?

오늘 체이닝·개방 주소법·리사이징을 손으로 짰지만, 실전 코테에선 dict·set·Counter를 그냥 씁니다. 연결 리스트 때와 똑같은 질문이 또 나오죠 — "안 쓸 걸 왜 배우나?" 이번엔 카테고리 B 전체(스택·큐·연결 리스트·해시)를 돌아보며 답해 보세요. 직접 구현이 준 게 "그 자료구조를 짜는 능력"이 아니라 "빅오를 따져 도구를 고르는 눈"이라면, 그 눈이 구체적으로 무엇인지(왜 dict의 in은 O(1)이고 list의 in은 O(n)인지를 설명할 수 있는 것, 시간 초과를 만났을 때 무엇을 의심할지 아는 것) 정리해 보세요. 그리고 다음 카테고리(트리·그래프)에서 이 "직접 구현으로 원리, 내장으로 실전"의 두 트랙이 어떻게 이어질지도 그려 보세요.