고급 자료구조와 알고리즘: 실전 시스템 구현
해시, 힙, B-트리 — 어디에 쓰이는지 알고 나니까 이해가 됐다
배열이랑 리스트, 기본 정렬까지는 코딩 문제 풀면서 자연스럽게 익혔는데, 해시 테이블이나 힙, B-트리 같은 건 처음에 “이걸 왜 따로 공부해야 하지?”라는 생각이 들었습니다.
그런데 면접 준비하면서 “Python 딕셔너리가 내부적으로 어떻게 동작하느냐”, “데이터베이스 인덱스는 왜 B-트리를 쓰느냐” 같은 질문을 만나고 나서 생각이 바뀌었습니다. 알고 보니 매일 쓰는 도구들 안에 이 구조들이 들어있었습니다.
해시 테이블
Python의 dict, Java의 HashMap이 이겁니다. 키를 넣으면 값이 바로 나오는 O(1) 조회가 가능한 구조입니다.
해시 함수가 하는 일
키를 받아서 배열의 인덱스로 변환합니다.
def simple_hash(key, table_size):
return sum(ord(char) for char in str(key)) % table_size
print(simple_hash("hello", 10)) # 2
print(simple_hash("world", 10)) # 1문제는 서로 다른 키가 같은 인덱스로 매핑될 수 있다는 겁니다. 이걸 충돌이라고 하는데, 충돌을 어떻게 처리하느냐에 따라 구현 방식이 갈립니다.
체이닝 방식
같은 인덱스에 여러 값이 오면 리스트로 이어 붙입니다.
class HashTableChaining:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)] # 리스트의 리스트
def _hash(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash(key)
# 기존 키가 있으면 업데이트
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value)
return
# 새 키면 추가
self.table[index].append((key, value))
def get(self, key):
index = self._hash(key)
for k, v in self.table[index]:
if k == key:
return v
return None
def remove(self, key):
index = self._hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
del self.table[index][i]
return True
return False
# 테스트
ht = HashTableChaining(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple")) # 5
print(ht.get("banana")) # 7구현이 직관적이고, 테이블이 꽉 차도 그냥 리스트가 길어지는 거라 크래시가 안 납니다. Python의 dict도 예전에는 이 방식을 썼습니다(지금은 오픈 어드레싱으로 바뀜).
개방 주소법
충돌이 나면 빈 자리를 찾아서 거기에 넣습니다.
class HashTableOpenAddressing:
def __init__(self, size):
self.size = size
self.table = [None] * size
self.deleted = object() # 삭제 표시용
def _hash(self, key):
return hash(key) % self.size
def _probe(self, index, i):
return (index + i) % self.size
def insert(self, key, value):
index = self._hash(key)
for i in range(self.size):
probe_index = self._probe(index, i)
if (self.table[probe_index] is None or
self.table[probe_index] is self.deleted):
self.table[probe_index] = (key, value)
return True
if self.table[probe_index][0] == key:
self.table[probe_index] = (key, value)
return True
return False # 테이블이 가득 참
def get(self, key):
index = self._hash(key)
for i in range(self.size):
probe_index = self._probe(index, i)
if self.table[probe_index] is None:
return None
if (self.table[probe_index] is not self.deleted and
self.table[probe_index][0] == key):
return self.table[probe_index][1]
return None
# 테스트
ht = HashTableOpenAddressing(10)
ht.insert("apple", 5)
ht.insert("banana", 7)
print(ht.get("apple")) # 5삭제가 좀 까다롭습니다. 그냥 None으로 만들면 그 뒤에 있던 값을 못 찾게 되니까, 삭제 표시(tombstone)를 따로 둬야 합니다. 이 부분에서 처음에 버그를 한참 찾았던 기억이 납니다.
해시 함수 설계
좋은 해시 함수는 값을 고르게 분산시켜서 충돌을 줄입니다.
def djb2_hash(key):
hash_value = 5381
for char in str(key):
hash_value = ((hash_value << 5) + hash_value) + ord(char)
return hash_value
def sdbm_hash(key):
hash_value = 0
for char in str(key):
hash_value = ord(char) + (hash_value << 6) + (hash_value << 16) - hash_value
return hash_value
def combined_hash(key, table_size):
h1 = djb2_hash(key)
h2 = sdbm_hash(key)
return (h1 + h2) % table_sizeDJB2가 유명한 건 간단한데 분산이 꽤 잘 된다는 이유 때문입니다. 5381이라는 초기값이 왜 하필 저 숫자인지 찾아봤는데, Dan Bernstein이 실험적으로 정한 거라고 합니다. 수학적 증명이 있는 건 아닌 것 같습니다.
힙과 우선순위 큐
힙은 “가장 크거나 작은 값을 빠르게 꺼내야 할 때” 쓰는 구조입니다. 완전 이진 트리 형태이고, 부모가 항상 자식보다 크면 최대힙, 작으면 최소힙입니다.
힙 정렬
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
# 왼쪽 자식이 더 큰 경우
if left < n and arr[left] > arr[largest]:
largest = left
# 오른쪽 자식이 더 큰 경우
if right < n and arr[right] > arr[largest]:
largest = right
# largest가 루트가 아닌 경우 교환
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 최대 힙 구성
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 힙에서 요소를 하나씩 추출
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # 최대값을 끝으로 이동
heapify(arr, i, 0) # 힙 속성 복원
# 테스트
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("힙 정렬 결과:", arr)힙 정렬은 O(n log n)이고 추가 메모리도 O(1)이라 이론적으로 좋은데, 실전에서는 퀵 정렬에 밀리는 경우가 많습니다. 캐시 지역성 때문이라고 하는데, 힙은 배열 안에서 접근하는 인덱스가 이곳저곳 뛰어다녀서 CPU 캐시에 불리하다고 합니다.
우선순위 큐
다익스트라 같은 알고리즘에서 “현재 가장 가까운 노드”를 빠르게 꺼내야 할 때 씁니다.
import heapq
class PriorityQueue:
def __init__(self):
self.heap = []
self.entry_count = 0
def push(self, priority, item):
entry = (priority, self.entry_count, item)
heapq.heappush(self.heap, entry)
self.entry_count += 1
def pop(self):
if self.heap:
return heapq.heappop(self.heap)[2]
return None
def peek(self):
if self.heap:
return self.heap[0][2]
return None
def is_empty(self):
return len(self.heap) == 0
# 테스트
pq = PriorityQueue()
pq.push(3, "low")
pq.push(1, "high")
pq.push(2, "medium")
print(pq.pop()) # "high" (우선순위 1)
print(pq.pop()) # "medium" (우선순위 2)entry_count를 넣는 이유는 우선순위가 같을 때 비교 에러를 방지하기 위해서입니다. 이거 없으면 priority가 같은 두 항목이 들어왔을 때 item끼리 비교하려다가 TypeError가 납니다. 처음에 이것 때문에 한참 헤맸습니다.
B-트리
데이터베이스 인덱스가 왜 이진 트리가 아니라 B-트리를 쓰는지 처음에 의문이었는데, 디스크 I/O와 관련이 있었습니다. 이진 트리는 노드 하나에 키가 하나라서 트리가 깊어지고, 깊어질수록 디스크 읽기 횟수가 늘어납니다. B-트리는 노드 하나에 키를 여러 개 넣어서 트리를 납작하게 만들고, 디스크 접근을 줄입니다.
class BTreeNode:
def __init__(self, leaf=False):
self.leaf = leaf
self.keys = []
self.children = []
class BTree:
def __init__(self, t=2):
self.root = BTreeNode(True)
self.t = t # 최소 차수
def search(self, key, node=None):
if node is None:
node = self.root
i = 0
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return True
if node.leaf:
return False
return self.search(key, node.children[i])
def insert(self, key):
root = self.root
if len(root.keys) == 2 * self.t - 1:
# 루트가 가득 찬 경우 분할
new_root = BTreeNode(False)
new_root.children.append(self.root)
self._split_child(new_root, 0)
self.root = new_root
self._insert_non_full(self.root, key)
def _insert_non_full(self, node, key):
i = len(node.keys) - 1
if node.leaf:
# 리프 노드에 삽입
node.keys.append(None)
while i >= 0 and key < node.keys[i]:
node.keys[i + 1] = node.keys[i]
i -= 1
node.keys[i + 1] = key
else:
# 내부 노드 처리
while i >= 0 and key < node.keys[i]:
i -= 1
i += 1
if len(node.children[i].keys) == 2 * self.t - 1:
self._split_child(node, i)
if key > node.keys[i]:
i += 1
self._insert_non_full(node.children[i], key)
def _split_child(self, parent, i):
t = self.t
y = parent.children[i]
z = BTreeNode(y.leaf)
# 새로운 노드에 키 이동
parent.children.insert(i + 1, z)
parent.keys.insert(i, y.keys[t - 1])
z.keys = y.keys[t: (2 * t) - 1]
y.keys = y.keys[0: t - 1]
if not y.leaf:
z.children = y.children[t: 2 * t]
y.children = y.children[0: t]
# 테스트
btree = BTree(t=2)
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
btree.insert(key)
print("B-트리에서 12 검색:", btree.search(12)) # True
print("B-트리에서 15 검색:", btree.search(15)) # FalseMySQL의 InnoDB가 B+트리(B-트리의 변형)를 쓰고, PostgreSQL도 기본 인덱스가 B-트리입니다. CREATE INDEX를 할 때마다 내부적으로 이 구조가 만들어지는 겁니다.
인덱스 종류별 특성을 정리하면:
- B-트리 인덱스: 범위 검색에 좋음 (WHERE price BETWEEN 100 AND 200)
- 해시 인덱스: 정확히 일치하는 검색에 좋음 (WHERE id = 42)
- 비트맵 인덱스: 값의 종류가 적은 컬럼에 좋음 (WHERE gender = ‘M’)
비교 기반이 아닌 정렬들
퀵 정렬이나 병합 정렬은 원소끼리 비교해서 정렬하기 때문에 아무리 빨라도 O(n log n)이 한계입니다. 그런데 조건이 맞으면 그보다 빠르게 정렬할 수 있는 방법이 있습니다.
계수 정렬
값의 범위가 제한돼 있을 때 씁니다. 각 값이 몇 번 나왔는지 세서 정렬합니다.
def counting_sort(arr):
if not arr:
return arr
# 범위 파악
max_val = max(arr)
min_val = min(arr)
range_val = max_val - min_val + 1
# 계수 배열 생성
count = [0] * range_val
output = [0] * len(arr)
# 빈도 계산
for num in arr:
count[num - min_val] += 1
# 누적 합 계산
for i in range(1, len(count)):
count[i] += count[i - 1]
# 정렬된 배열 생성
for num in reversed(arr):
output[count[num - min_val] - 1] = num
count[num - min_val] -= 1
return output
# 테스트
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("계수 정렬 결과:", sorted_arr)O(n + k)입니다. k는 값의 범위인데, 범위가 n에 비해 너무 크면 오히려 비효율적입니다. 예를 들어 [1, 1000000] 두 개를 정렬하는 데 백만 크기의 배열을 만드는 건 낭비니까요.
기수 정렬
자릿수별로 계수 정렬을 반복합니다.
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# 현재 자릿수 빈도 계산
for num in arr:
digit = (num // exp) % 10
count[digit] += 1
# 누적 합 계산
for i in range(1, 10):
count[i] += count[i - 1]
# 정렬
for i in range(n - 1, -1, -1):
digit = (arr[i] // exp) % 10
output[count[digit] - 1] = arr[i]
count[digit] -= 1
return output
def radix_sort(arr):
if not arr:
return arr
# 최대값 찾기
max_val = max(arr)
# 각 자릿수별 정렬
exp = 1
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
# 테스트
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print("기수 정렬 결과:", sorted_arr)일의 자리부터 정렬하고, 십의 자리, 백의 자리… 이렇게 올라가는데, 각 단계에서 안정 정렬(같은 값의 순서가 유지되는 정렬)을 써야 합니다. 처음에 이 부분을 놓쳐서 결과가 이상하게 나왔었습니다.
AVL 트리
이진 탐색 트리의 문제는, 값이 정렬된 순서로 들어오면 한쪽으로 쏠려서 사실상 연결 리스트가 된다는 겁니다. AVL 트리는 삽입/삭제할 때마다 균형을 맞춰서 항상 O(log n)을 보장합니다.
class AVLNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def get_height(self, node):
return node.height if node else 0
def get_balance(self, node):
if not node:
return 0
return self.get_height(node.left) - self.get_height(node.right)
def rotate_right(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
return x
def rotate_left(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(self.get_height(x.left), self.get_height(x.right))
y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))
return y
def insert(self, root, key):
if not root:
return AVLNode(key)
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))
balance = self.get_balance(root)
# 불균형 처리
if balance > 1 and key < root.left.key: # LL
return self.rotate_right(root)
if balance < -1 and key > root.right.key: # RR
return self.rotate_left(root)
if balance > 1 and key > root.left.key: # LR
root.left = self.rotate_left(root.left)
return self.rotate_right(root)
if balance < -1 and key < root.right.key: # RL
root.right = self.rotate_right(root.right)
return self.rotate_left(root)
return root
# 테스트
avl = AVLTree()
root = None
for key in [10, 20, 30, 40, 50, 25]:
root = avl.insert(root, key)회전 로직이 처음에 직관적으로 안 와닿았습니다. LL, RR은 그래도 한 방향이라 그리기 쉬운데, LR이랑 RL은 두 번 회전해야 해서 종이에 그려보지 않으면 헷갈립니다. 실무에서는 AVL보다 레드-블랙 트리를 더 많이 쓴다고 하는데(Java의 TreeMap이 레드-블랙), AVL이 재균형을 더 자주 해서 검색은 빠르지만 삽입/삭제가 좀 느리기 때문이라고 합니다.
실전에서 만나는 구조들
LRU 캐시
“가장 최근에 안 쓴 걸 먼저 버린다”는 전략의 캐시입니다. 브라우저 캐시, Redis의 maxmemory-policy 등 여기저기서 쓰입니다.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
# 최근에 사용된 것으로 이동
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
# 기존 값 업데이트
self.cache.move_to_end(key)
else:
# 새 값 추가
if len(self.cache) >= self.capacity:
# 가장 오래된 항목 제거
self.cache.popitem(last=False)
self.cache[key] = value
self.cache.move_to_end(key)
# 테스트
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 1
cache.put(3, 3) # 2 제거
print(cache.get(2)) # -1 (제거됨)LeetCode에 LRU Cache 문제가 있는데, OrderedDict 없이 직접 해시맵 + 이중 연결 리스트로 구현하는 버전도 풀어보면 좋습니다. 구조가 왜 이렇게 생겼는지 이해가 됩니다.
블룸 필터
“이 원소가 집합에 있는가?”를 아주 빠르게, 하지만 약간의 오차를 허용하면서 답하는 구조입니다. “없다”고 하면 확실히 없고, “있다”고 하면 실제로는 없을 수도 있습니다(거짓 양성).
import hashlib
class BloomFilter:
def __init__(self, size, hash_count):
self.size = size
self.hash_count = hash_count
self.bit_array = [0] * size
def _hashes(self, item):
hashes = []
for i in range(self.hash_count):
hash_obj = hashlib.md5((str(item) + str(i)).encode())
hash_val = int(hash_obj.hexdigest(), 16) % self.size
hashes.append(hash_val)
return hashes
def add(self, item):
for hash_val in self._hashes(item):
self.bit_array[hash_val] = 1
def check(self, item):
for hash_val in self._hashes(item):
if self.bit_array[hash_val] == 0:
return False # 확실히 없음
return True # 있을 수 있음
# 테스트
bf = BloomFilter(100, 3)
bf.add("apple")
bf.add("banana")
print("apple 존재:", bf.check("apple")) # True
print("banana 존재:", bf.check("banana")) # True
print("orange 존재:", bf.check("orange")) # False (거짓 음성 없음)처음에 “틀릴 수 있는 자료구조를 왜 쓰지?” 싶었는데, 메모리를 극단적으로 아낄 수 있다는 게 핵심이었습니다. Chrome이 악성 URL 체크할 때, Cassandra가 디스크 읽기 전에 데이터 존재 여부를 확인할 때 블룸 필터를 씁니다. “일단 없는 건 빠르게 걸러내고, 있을 수도 있는 것만 정확히 확인하자”는 전략입니다.
성능 비교
구조를 고를 때 결국 보게 되는 건 이런 부분입니다.
해시 테이블: 평균 O(1) 조회인데, 충돌이 심해지면 O(n)까지 갈 수 있습니다. 적재율(load factor)을 0.75 이하로 유지하는 게 일반적입니다. Python dict는 2/3을 기준으로 리사이징합니다.
트리 구조들: AVL은 O(log n) 보장, B-트리는 디스크 I/O 최적화가 목적, 레드-블랙 트리는 AVL보다 삽입/삭제에서 유리합니다.
캐시 전략: LRU가 가장 흔하고, LFU(자주 쓴 걸 유지)도 있고, ARC(LRU + LFU 혼합)도 있습니다. 어떤 게 좋은지는 접근 패턴에 따라 다릅니다.
연습 문제
-
해시 테이블에서 충돌이 발생하는 이유와 해결 방법을 설명하세요.
-
힙 정렬의 시간 복잡도를 분석하고, 다른 정렬 알고리즘과 비교해보세요.
-
B-트리가 데이터베이스 인덱스로 적합한 이유를 설명하세요.
-
블룸 필터가 “거짓 양성”을 허용하는 이유와 장점을 설명하세요.
결국 중요한 건 고르는 감각
이것들을 전부 처음부터 구현할 일은 거의 없습니다. Python에는 dict가 있고, heapq가 있고, DB가 알아서 인덱스를 관리해줍니다. 그래도 내부 구조를 아는 것과 모르는 것의 차이는, 문제가 생겼을 때 드러납니다. “왜 이 쿼리가 느리지?” 했을 때 인덱스 구조를 알면 원인을 짐작할 수 있고, “메모리가 부족한데 조회는 빨라야 해” 같은 상황에서 블룸 필터를 떠올릴 수 있는 건 한 번이라도 공부해본 덕분입니다.