05. Algorithm_Hash Tables and Dynamic Programming

학습 목표

• 해시 함수의 조건과 나누기, 곱하기 방법
• 충돌 해결: 체이닝과 개방 주소법(선형 조사, 이차 조사, 더블 해싱), 1차/2차 군집
• 개방 주소법의 삭제(DELETED 표식)와 적재율, 재해싱
• 적재율에 따른 평균 조사 횟수를 실험으로 확인
• 동적 프로그래밍을 쓸 수 있는 두 조건
• 피보나치, 행렬 경로, 조약돌 놓기 문제를 DP로 풀고 전수 탐색과 비교

---

1. 해시 테이블

원소의 키를 해시 함수로 계산한 위치에 바로 저장하는 구조. 평균적으로 검색, 삽입, 삭제가 \(O(1)\)이지만, 원소 사이의 순서 정보가 없어서 최솟값 찾기 같은 연산은 지원하지 않음.

해시 함수

해시 함수는 원소를 테이블에 고루 퍼뜨리면서 계산이 간단해야 함.

방법	함수	테이블 크기 m
나누기	\(h(x) = x \bmod m\)	2의 거듭제곱에 가깝지 않은 소수가 좋음
곱하기	\(h(x) = \lfloor m (xA \bmod 1) \rfloor\) (\(0 < A < 1\))	소수일 필요 없음, 보통 \(2^p\)

충돌과 해결

충돌: 저장하려는 칸에 이미 다른 원소가 있는 경우. 충돌이 많으면 빠른 검색이라는 장점이 사라짐.

체이닝

• 같은 주소로 해싱되는 원소들을 연결 리스트 하나로 관리하고, 새 원소는 리스트 맨 앞에 삽입
• 테이블이 꽉 차도 계속 넣을 수 있음 (적재율이 1을 넘어도 됨)
• 리스트 관리에 메모리가 더 들고, 한 리스트가 길어지면 검색이 느려짐

개방 주소법: 충돌이 나면 테이블 안에서 빈자리를 찾을 때까지 다음 주소를 계속 계산함. 추가 메모리가 필요 없지만 적재율이 1을 넘을 수 없음.

방법	\(i\)번째 조사 위치	특징
선형 조사	\((h(x) + i) \bmod m\)	바로 옆 칸부터 차례로. 원소들이 덩어리로 뭉치는 1차 군집이 생기고, 덩어리가 클수록 더 커짐
이차 조사	\((h(x) + i^2) \bmod m\)	보폭이 커져 1차 군집은 피하지만, 처음 해시 값이 같은 원소들은 같은 순서로 조사하는 2차 군집이 남음
더블 해싱	\((h(x) + i \cdot f(x)) \bmod m\)	두 번째 함수 \(f(x)\)로 보폭을 정함. 처음 해시 값이 같아도 \(f(x)\)까지 같을 확률은 낮아 2차 군집도 예방

개방 주소법의 삭제

원소를 지운 칸을 그냥 비우면, 그 칸을 지나서 저장된 원소를 검색할 때 빈칸에서 “없다”고 멈춰 버림. 그래서 지운 칸에는 DELETED 표식을 남겨 검색은 계속 지나가게 함. 표식 때문에 공간이 낭비되지만, 검색의 정확성을 지키는 대가.

적재율과 성능

적재율 \(\alpha = n / m\) (테이블 크기 \(m\), 원소 \(n\)개)

방법	성공 검색	실패 검색
체이닝	\(1 + \frac{\alpha}{2} - \frac{\alpha}{2n}\)	\(\alpha\)
선형 조사	\(\frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)\)	\(\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)\)

적재율이 높아지면 개방 주소법은 성능이 급격히 나빠져서 \(O(1)\)에서 \(O(n)\) 쪽으로 감. 그래서 적재율이 일정 수준을 넘으면 테이블을 2배로 늘리고 모든 원소를 다시 해싱함.

적재율별 조사 횟수 (실행)

테이블 크기 10,007에 적재율만큼 무작위 키를 넣고, 저장된 키(성공 검색)와 없는 키(실패 검색)의 평균 조사 횟수를 셈. 체이닝은 리스트에서 비교한 원소 수.

import random

M = 10007                                     # 테이블 크기 (소수)

def h1(x): return x % M
def h2(x): return 1 + x % (M - 2)             # 더블 해싱용 두 번째 함수 (0이 되지 않게)

def probe_seq(x, i, method):
    if method == "linear":    return (h1(x) + i) % M
    if method == "quadratic": return (h1(x) + i * i) % M
    if method == "double":    return (h1(x) + i * h2(x)) % M

def insert_open(table, x, method):
    for i in range(M):
        j = probe_seq(x, i, method)
        if table[j] is None:
            table[j] = x; return i + 1
    raise RuntimeError("table full")

def search_open(table, x, method):            # 조사 횟수 반환 (빈 칸을 만나면 실패)
    for i in range(M):
        j = probe_seq(x, i, method)
        if table[j] is None: return i + 1
        if table[j] == x: return i + 1
    return M

def experiment(alpha, seed=0):
    rng = random.Random(seed)
    n = int(alpha * M)
    keys = rng.sample(range(10**9), n)
    absent = rng.sample(range(10**9, 2 * 10**9), 2000)
    res = {}
    # 체이닝: 리스트 길이로 조사 횟수 계산 (맨 앞 삽입)
    chains = [[] for _ in range(M)]
    for x in keys: chains[h1(x)].insert(0, x)
    res["chaining"] = (sum(chains[h1(x)].index(x) + 1 for x in keys) / n,
                       sum(len(chains[h1(x)]) for x in absent) / len(absent))
    for m in ("linear", "quadratic", "double"):
        t = [None] * M
        for x in keys: insert_open(t, x, m)
        res[m] = (sum(search_open(t, x, m) for x in keys) / n,
                  sum(search_open(t, x, m) for x in absent) / len(absent))
    return res

print(f"테이블 크기 m = {M}, 평균 조사 횟수 (성공 검색 / 실패 검색)")
print(f"{'alpha':>5} {'chaining':>14} {'linear':>14} {'quadratic':>14} {'double':>14} {'linear 이론':>16}")
for a in (0.3, 0.5, 0.7, 0.9, 0.95):
    r = experiment(a)
    th = (0.5 * (1 + 1 / (1 - a)), 0.5 * (1 + 1 / (1 - a) ** 2))
    print(f"{a:>5} " + " ".join(f"{s:>6.2f} /{f:>6.2f}" for s, f in r.values()) + f"   {th[0]:>5.2f} /{th[1]:>6.2f}")

실행 결과

테이블 크기 m = 10007, 평균 조사 횟수 (성공 검색 / 실패 검색)
alpha       chaining         linear      quadratic         double        linear 이론
  0.3   1.15 /  0.28   1.21 /  1.48   1.20 /  1.43   1.18 /  1.42    1.21 /  1.52
  0.5   1.25 /  0.49   1.51 /  2.48   1.44 /  2.12   1.39 /  2.01    1.50 /  2.50
  0.7   1.35 /  0.71   2.21 /  6.39   1.81 /  3.84   1.72 /  3.34    2.17 /  6.06
  0.9   1.46 /  0.90   5.15 / 47.79   2.80 / 11.80   2.54 / 10.03    5.50 / 50.50
 0.95   1.48 /  0.95  10.76 /310.08   3.59 / 24.18   3.14 / 20.10   10.50 /200.50

• 선형 조사의 실험값이 이론식과 거의 같음. \(\alpha = 0.9\)이면 실패 검색 한 번에 평균 48번, 0.95면 310번을 조사함
• 같은 적재율에서 이차 조사, 더블 해싱 순으로 군집이 줄어 조사 횟수가 적음 (\(\alpha = 0.9\) 실패 검색: 47.8 → 11.8 → 10.0)
• 체이닝은 \(\alpha\)가 커져도 성공 검색이 약 \(1 + \alpha/2\), 실패 검색이 약 \(\alpha\)로 완만하게 늘어남
• 정리하면 테이블이 널널할 때(작은 \(\alpha\))는 리스트 관리 비용이 없는 개방 주소법도 충분하고, 테이블이 꽉 찰수록 체이닝이 유리함

---

2. 동적 프로그래밍

작은 문제들을 풀다 보면 같은 문제가 반복해서 나타남. 한 번 계산한 값을 저장해 두었다가 재사용(메모이제이션)해서 중복 계산을 없애는 기법.

• 퀵 정렬, 병합 정렬, 팩토리얼, DFS처럼 부분 문제가 겹치지 않으면 재귀가 효율적
• 피보나치, 행렬 곱셈 순서처럼 같은 계산이 수없이 반복되면 재귀가 매우 비효율적

(중요!!) DP를 적용할 수 있는 두 조건

1. 최적 부분 구조: 큰 문제의 최적해가 작은 문제의 최적해를 포함함
2. 재귀 호출 시 심한 중복: 재귀로 풀면 같은 작은 문제에 대한 호출이 심하게 중복됨

행렬 경로 문제

\(n \times n\) 행렬의 왼쪽 위에서 오른쪽 아래까지 오른쪽이나 아래로만 이동할 때, 지나간 칸의 합이 최대가 되는 경로.

• \((i, j)\)까지 오는 최대 합을 \(c_{ij}\)라고 하면, 그 칸에는 위 \((i-1, j)\)나 왼쪽 \((i, j-1)\)에서만 올 수 있음
• 점화식은 \(c_{ij} = m_{ij} + \max(c_{i-1,j},\ c_{i,j-1})\)
• 칸마다 한 번씩 계산하므로 \(O(n^2)\). 모든 경로를 보면 \(\binom{2n-2}{n-1}\)개라 지수 시간

조약돌 놓기

\(3 \times n\) 테이블의 각 칸에 점수가 있고, 조약돌을 놓은 칸의 점수를 얻음. 같은 열에서 세로로 인접하거나, 이웃한 열에서 가로로 인접하게 놓을 수 없음.

• 한 열에 놓을 수 있는 패턴은 4가지: 위, 가운데, 아래, 위+아래
• 패턴 \(p\)와 \(q\)가 양립한다는 것은 이웃한 열에 놓아도 가로로 인접하지 않는다는 뜻 (같은 행을 쓰지 않음)
• \(peb(i, p)\)를 \(i\)열을 패턴 \(p\)로 놓을 때 \(1 \sim i\)열의 최대 점수라고 하면, 점화식은 \(peb(i, p) = w(i, p) + \max_{q} peb(i-1, q)\)이고 \(q\)는 \(p\)와 양립하는 패턴
• 열마다 패턴 4개 × 이전 패턴 최대 4개를 보므로 \(O(n)\)

세 문제 실행

import itertools, random
from functools import lru_cache

# 1) 피보나치: 단순 재귀 vs 메모이제이션 vs 상향식
calls = 0
def fib_rec(n):
    global calls; calls += 1
    return n if n < 2 else fib_rec(n - 1) + fib_rec(n - 2)

@lru_cache(None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

def fib_dp(n):
    f = [0, 1] + [0] * max(0, n - 1)
    for i in range(2, n + 1): f[i] = f[i - 1] + f[i - 2]
    return f[n]

for n in (10, 20, 30):
    calls = 0; v = fib_rec(n)
    print(f"fib({n}) = {v}: 단순 재귀 호출 {calls:,}번, DP 계산 {n - 1}번, 결과 일치 {v == fib_memo(n) == fib_dp(n)}")

# 2) 행렬 경로: 왼쪽 위 → 오른쪽 아래, 오른쪽 또는 아래로만 이동, 지나간 칸의 합 최대
def matrix_path(m):
    n = len(m)
    c = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            c[i][j] = m[i - 1][j - 1] + max(c[i - 1][j], c[i][j - 1])   # 위에서 오거나 왼쪽에서 오거나
    return c[n][n]

def matrix_path_brute(m):
    n, best = len(m), 0
    for downs in itertools.combinations(range(2 * n - 2), n - 1):       # 이동 2n-2번 중 아래로 갈 n-1번 선택
        i = j = 0; s = m[0][0]
        for step in range(2 * n - 2):
            if step in downs: i += 1
            else: j += 1
            s += m[i][j]
        best = max(best, s)
    return best

M = [[6, 7, 12, 5], [5, 3, 11, 18], [7, 17, 3, 3], [8, 10, 14, 9]]
print(f"\n행렬 경로 최대 합: DP {matrix_path(M)}, 모든 경로 탐색 {matrix_path_brute(M)}")

# 3) 조약돌 놓기: 3 x n 테이블, 같은 열에서 세로로 인접 금지, 옆 열에서 가로로 인접 금지
PATTERNS = {1: (0,), 2: (1,), 3: (2,), 4: (0, 2)}             # 한 열에 놓을 수 있는 4가지 패턴
def compatible(p, q):                                         # 이웃한 열에서 같은 행을 쓰지 않으면 양립
    return not set(PATTERNS[p]) & set(PATTERNS[q])

def pebble(w):                                               # w[r][c]: r행 c열의 점수
    n = len(w[0])
    val = lambda c, p: sum(w[r][c] for r in PATTERNS[p])
    peb = {p: val(0, p) for p in PATTERNS}                   # peb[p]: c열을 패턴 p로 끝낼 때 최대 점수
    for c in range(1, n):
        peb = {p: val(c, p) + max(peb[q] for q in PATTERNS if compatible(p, q)) for p in PATTERNS}
    return max(peb.values())

def pebble_brute(w):
    n, best = len(w[0]), float("-inf")
    for seq in itertools.product(PATTERNS, repeat=n):
        if all(compatible(seq[c], seq[c + 1]) for c in range(n - 1)):
            best = max(best, sum(w[r][c] for c, p in enumerate(seq) for r in PATTERNS[p]))
    return best

W = [[6, 7, 12, -5, 5, 3, 11, 3], [-8, 10, 14, 9, 7, 13, 8, 5], [11, 12, 7, 4, 8, -2, 9, 4]]
print(f"조약돌 놓기 최대 점수: DP {pebble(W)}, 모든 배치 탐색 {pebble_brute(W)}")
random.seed(0)
ok = all(pebble(w) == pebble_brute(w) for w in
         ([[random.randint(-10, 20) for _ in range(6)] for _ in range(3)] for _ in range(200)))
print("무작위 테이블 200개에서 DP와 전수 탐색 결과 일치:", ok)

실행 결과

fib(10) = 55: 단순 재귀 호출 177번, DP 계산 9번, 결과 일치 True
fib(20) = 6765: 단순 재귀 호출 21,891번, DP 계산 19번, 결과 일치 True
fib(30) = 832040: 단순 재귀 호출 2,692,537번, DP 계산 29번, 결과 일치 True

행렬 경로 최대 합: DP 68, 모든 경로 탐색 68
조약돌 놓기 최대 점수: DP 106, 모든 배치 탐색 106
무작위 테이블 200개에서 DP와 전수 탐색 결과 일치: True

• 단순 재귀 피보나치는 \(n = 30\)에서 약 270만 번 호출하지만, DP는 29번 덧셈으로 끝남. 호출 수가 \(n\)이 10 늘 때마다 약 120배씩 늘어나는 지수 증가
• 행렬 경로와 조약돌 놓기는 가능한 경우를 모두 확인한 결과와 DP 결과가 같음. 조약돌 놓기는 무작위 테이블 200개에서도 모두 일치

---

정리 노트에서 정정한 부분 정리

위치	원래	정정	이유
나누기 방법	m은 보통 소수	2의 거듭제곱에 가깝지 않은 소수	2의 거듭제곱에 가까우면 키의 하위 비트만 반영되어 고루 퍼지지 않음
결론	α < 0.3이면 개방 주소법, α > 0.5면 체이닝이 더 빠름	조사 횟수는 모든 α에서 체이닝이 적음(실험). 개방 주소법이 빠를 수 있는 것은 포인터를 따라가지 않아 실제 메모리 접근이 빠르기 때문	실험 결과 α = 0.3에서도 체이닝 1.15회, 선형 조사 1.21회

---

최종 핵심 정리

1. 해시 테이블은 평균 \(O(1)\)로 검색, 삽입, 삭제를 하지만 최솟값 찾기 같은 순서 연산은 지원하지 않음
2. 해시 함수는 나누기 \(x \bmod m\)(m은 소수)와 곱하기 \(\lfloor m(xA \bmod 1) \rfloor\)(m은 보통 \(2^p\))가 있음
3. 체이닝은 같은 주소의 원소를 연결 리스트로 묶고, 개방 주소법은 테이블 안에서 빈칸을 찾음
4. 선형 조사는 1차 군집, 이차 조사는 2차 군집이 생기고, 더블 해싱은 두 번째 함수로 둘 다 줄임
5. 개방 주소법에서 지운 칸에는 DELETED 표식을 남겨야 검색이 끊기지 않음
6. 적재율 \(\alpha\)가 1에 가까워지면 개방 주소법의 조사 횟수가 폭증하므로(α = 0.95 실패 검색 310번) 테이블을 2배로 늘려 재해싱함
7. DP는 최적 부분 구조와 중복되는 부분 문제가 있을 때 쓰고, 계산한 값을 저장해 재사용함
8. 행렬 경로는 \(c_{ij} = m_{ij} + \max(c_{i-1,j}, c_{i,j-1})\)로 \(O(n^2)\), 조약돌 놓기는 양립 패턴의 최댓값으로 \(O(n)\)

---

End.