더 나아가기 코드
노트의 개념을 Python 3로 옮긴 코드다. 표준 라이브러리만 쓰고, 파일 끝의 assert 예제가 그대로 실행된다. 복사해 python3 파일이름.py로 돌려 보자.
LRU 캐시
"""LRU 캐시: 해시 맵(키 → 노드)과 이중 연결 리스트(쓴 순서)를 겹쳐 get·put을 O(1)에 한다.
시간: get·put 모두 O(1) — 맵 조회 한 번과 포인터 몇 개 바꾸기
공간: O(capacity)
"""
from __future__ import annotations
class Node:
"""리스트 노드. 내보낼 때 맵에서도 지우려고 키를 함께 든다."""
def __init__(self, key: str = "", value: object = None) -> None:
self.key = key
self.value = value
self.previous: Node | None = None
self.next: Node | None = None
class LruCache:
"""칸이 차면 가장 오래 안 쓴 것부터 내보내는 캐시. head 쪽이 가장 최근이다."""
def __init__(self, capacity: int) -> None:
if capacity < 1:
raise ValueError("capacity는 1 이상이어야 한다")
self.capacity = capacity
self.nodes: dict[str, Node] = {}
# 값이 없는 보초(sentinel) 노드를 양 끝에 두어 빈 리스트·맨 앞 같은 예외 처리를 없앤다
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.previous = self.head
def _unlink(self, node: Node) -> None:
"""노드를 리스트에서 뗀다."""
node.previous.next = node.next
node.next.previous = node.previous
def _push_front(self, node: Node) -> None:
"""노드를 head 바로 뒤에 붙인다."""
node.previous = self.head
node.next = self.head.next
self.head.next.previous = node
self.head.next = node
def get(self, key: str) -> object | None:
"""값을 돌려주고 그 노드를 맨 앞으로 옮긴다. 없으면 None이다."""
node = self.nodes.get(key)
if node is None:
return None
self._unlink(node)
self._push_front(node)
return node.value
def put(self, key: str, value: object) -> str | None:
"""값을 넣거나 바꾸고 맨 앞에 둔다. 내보낸 키가 있으면 돌려준다."""
node = self.nodes.get(key)
if node is not None:
node.value = value
self._unlink(node)
self._push_front(node)
return None
evicted = None
if len(self.nodes) >= self.capacity:
oldest = self.tail.previous
self._unlink(oldest)
del self.nodes[oldest.key]
evicted = oldest.key
node = Node(key, value)
self._push_front(node)
self.nodes[key] = node
return evicted
def keys(self) -> list[str]:
"""최근에 쓴 순서대로 키를 돌려준다."""
result = []
node = self.head.next
while node is not self.tail:
result.append(node.key)
node = node.next
return result
if __name__ == "__main__":
cache = LruCache(3)
for key in "ABC":
assert cache.put(key, key.lower()) is None
assert cache.get("A") == "a"
assert cache.put("D", "d") == "B"
assert cache.get("C") == "c"
assert cache.put("E", "e") == "A"
assert cache.get("B") is None
assert cache.keys() == ["E", "C", "D"]
# 칸보다 키가 하나 많은 순환 접근은 한 번도 적중하지 않는다
scan = LruCache(3)
hits = 0
for key in "ABCDABCD":
if scan.get(key) is not None:
hits += 1
else:
scan.put(key, key)
assert hits == 0
one = LruCache(1)
one.put("A", 1)
assert one.put("A", 2) is None
assert one.get("A") == 2
print("ok")스킵 리스트
"""스킵 리스트: 정렬된 연결 리스트 위에 듬성듬성한 층을 확률로 쌓아 찾기·넣기를 평균 O(log n)에 한다.
시간: 찾기·넣기 평균 O(log n), 최악 O(n) (동전이 계속 한쪽만 나올 때)
공간: 평균 O(n) — 노드당 평균 2층
"""
from __future__ import annotations
import random
MAX_LEVEL = 16
class Node:
"""키와 층마다의 다음 노드(forward[0]이 맨 아래층)."""
def __init__(self, key: int | None, level: int) -> None:
self.key = key
self.forward: list[Node | None] = [None] * level
class SkipList:
"""정수 키 집합. 같은 seed면 같은 모양이 나온다."""
def __init__(self, seed: int = 0, probability: float = 0.5) -> None:
self.random = random.Random(seed)
self.probability = probability
self.head = Node(None, MAX_LEVEL)
self.level = 1
def _random_level(self) -> int:
"""앞면이 나오는 동안 한 층씩 올린다."""
level = 1
while level < MAX_LEVEL and self.random.random() < self.probability:
level += 1
return level
def _predecessors(self, key: int) -> list[Node]:
"""층마다 key보다 작은 마지막 노드. 넣을 때 이 노드들의 포인터를 바꾼다."""
update = [self.head] * MAX_LEVEL
node = self.head
for level in range(self.level - 1, -1, -1):
while node.forward[level] is not None and node.forward[level].key < key:
node = node.forward[level]
update[level] = node
return update
def contains(self, key: int) -> bool:
"""key가 있는지 위층부터 건너뛰며 찾는다."""
candidate = self._predecessors(key)[0].forward[0]
return candidate is not None and candidate.key == key
def insert(self, key: int) -> bool:
"""key를 넣는다. 이미 있으면 False다."""
update = self._predecessors(key)
candidate = update[0].forward[0]
if candidate is not None and candidate.key == key:
return False
level = self._random_level()
self.level = max(self.level, level)
node = Node(key, level)
for index in range(level):
node.forward[index] = update[index].forward[index]
update[index].forward[index] = node
return True
def keys(self, level: int = 0) -> list[int]:
"""한 층의 키를 차례로 돌려준다."""
result = []
node = self.head.forward[level]
while node is not None:
result.append(node.key)
node = node.forward[level]
return result
if __name__ == "__main__":
values = [27, 2, 41, 14, 9, 33, 5, 20]
skip_list = SkipList(seed=42)
for value in values:
assert skip_list.insert(value)
assert not skip_list.insert(20)
assert skip_list.keys() == sorted(values)
assert skip_list.contains(27)
assert not skip_list.contains(30)
# 위층은 아래층의 부분 수열이다
for level in range(1, skip_list.level):
upper = skip_list.keys(level)
assert upper == sorted(upper)
assert set(upper) <= set(skip_list.keys(level - 1))
# 노드 수천 개여도 층은 log₂ n 근처에 머문다
big = SkipList(seed=7)
for value in random.Random(1).sample(range(100_000), 4096):
big.insert(value)
assert 8 <= big.level <= MAX_LEVEL
assert len(big.keys()) == 4096
assert SkipList().keys() == []
print("ok")HyperLogLog
"""HyperLogLog: 해시의 앞 비트로 통을 고르고, 나머지 비트에서 첫 1이 나온 자리(rank)의 최댓값으로 서로 다른 값의 수를 어림한다.
시간: 넣기 O(1), 추정 O(m) (m = 통 수)
공간: O(m) — 통마다 작은 정수 하나. 넣은 값의 수와 상관없다
"""
import hashlib
import math
def hash64(item: str) -> int:
"""값을 고르게 섞인 64비트 정수로 바꾼다."""
digest = hashlib.sha256(item.encode("utf-8")).digest()
return int.from_bytes(digest[:8], "big")
def alpha(buckets: int) -> float:
"""통 수에 따른 편향 보정 상수."""
if buckets == 16:
return 0.673
if buckets == 32:
return 0.697
if buckets == 64:
return 0.709
return 0.7213 / (1 + 1.079 / buckets)
class HyperLogLog:
"""통 2^bucket_bits개짜리 HyperLogLog."""
def __init__(self, bucket_bits: int = 10) -> None:
self.bucket_bits = bucket_bits
self.registers = [0] * (1 << bucket_bits)
def add(self, item: str) -> None:
"""값 하나를 본다. 같은 값은 해시가 같아 여러 번 넣어도 결과가 같다."""
hashed = hash64(item)
rest_bits = 64 - self.bucket_bits
bucket = hashed >> rest_bits
rest = hashed & ((1 << rest_bits) - 1)
# rank = 나머지 비트에서 왼쪽부터 첫 1이 나온 자리(모두 0이면 rest_bits + 1)
rank = rest_bits - rest.bit_length() + 1
self.registers[bucket] = max(self.registers[bucket], rank)
def merge(self, other: "HyperLogLog") -> None:
"""통마다 큰 값을 골라 합집합의 HyperLogLog로 만든다."""
if other.bucket_bits != self.bucket_bits:
raise ValueError("통 수가 같아야 합칠 수 있다")
self.registers = [max(mine, theirs) for mine, theirs in zip(self.registers, other.registers)]
def estimate(self) -> float:
"""서로 다른 값의 수를 추정한다."""
return estimate_from_registers(self.registers)
def estimate_from_registers(registers: list[int]) -> float:
"""조화 평균 추정. 작은 개수에서 빈 통이 있으면 빈 통 비율로 센다(linear counting)."""
buckets = len(registers)
harmonic = sum(2.0 ** -register for register in registers)
raw = alpha(buckets) * buckets * buckets / harmonic
empty = registers.count(0)
if raw <= 2.5 * buckets and empty > 0:
return buckets * math.log(buckets / empty)
return raw
if __name__ == "__main__":
# 문제 페이지의 손 계산과 같은 값
assert round(estimate_from_registers([2, 0, 3, 1]), 2) == 5.55
merged = [2, 3, 2, 3, 2, 4, 2, 2, 3, 4, 2, 2, 5, 3, 2, 3]
assert round(estimate_from_registers(merged), 1) == 61.9
counter = HyperLogLog(bucket_bits=10)
for index in range(20_000):
counter.add(f"user-{index}")
# 중복은 결과를 바꾸지 않는다
counter.add(f"user-{index % 100}")
estimate = counter.estimate()
# 표준 오차 1.04/√1024 ≈ 3.3%. 여유 있게 10% 안을 본다
assert abs(estimate - 20_000) / 20_000 < 0.10, estimate
left = HyperLogLog(bucket_bits=10)
right = HyperLogLog(bucket_bits=10)
for index in range(5_000):
left.add(f"a-{index}")
right.add(f"b-{index}")
left.merge(right)
assert abs(left.estimate() - 10_000) / 10_000 < 0.10
assert HyperLogLog(bucket_bits=4).estimate() == 0
print("ok")P와 NP
"""P와 NP: 부분집합 합 문제로 '답을 확인하기'(다항 시간)와 '답을 찾기'(지수 시간)를 비교한다.
시간: 확인 O(n) (증거의 수를 한 번 더한다), 단순 풀기 O(2ⁿ · n) (부분집합을 모두 시험한다)
공간: 확인 O(n), 풀기 O(n) (부분집합 하나씩 만든다)
"""
from itertools import combinations
def verify_subset_sum(values: list[int], target: int, certificate: list[int]) -> bool:
"""증거(인덱스 목록)가 서로 다른 유효한 인덱스이고, 그 값의 합이 target인지 확인한다."""
if len(set(certificate)) != len(certificate):
return False
if any(index < 0 or index >= len(values) for index in certificate):
return False
return sum(values[index] for index in certificate) == target
def solve_subset_sum(values: list[int], target: int) -> list[tuple[int, ...]]:
"""합이 target인 부분집합을 모두 시험해 인덱스 묶음으로 돌려준다(빈 집합 포함 2ⁿ개)."""
solutions = []
for size in range(len(values) + 1):
for indexes in combinations(range(len(values)), size):
if verify_subset_sum(values, target, list(indexes)):
solutions.append(indexes)
return solutions
def verify_vertex_cover(edges: list[tuple[int, int]], cover: set[int], limit: int) -> bool:
"""정점 덮개 결정 문제의 증거 확인: 크기가 limit 이하이고 모든 간선의 한쪽 끝이 cover에 있는가."""
return len(cover) <= limit and all(left in cover or right in cover for left, right in edges)
if __name__ == "__main__":
values = [12, 4, 9, 7, 15, 2]
assert verify_subset_sum(values, 23, [0, 2, 5])
assert not verify_subset_sum(values, 23, [1, 3, 4])
# 같은 원소를 두 번 쓴 증거는 거절한다
assert not verify_subset_sum(values, 30, [4, 4])
solutions = solve_subset_sum(values, 23)
assert solutions == [(0, 1, 3), (0, 2, 5)]
# 찾은 답은 모두 확인을 통과하고, 확인을 통과하는 답은 모두 찾는다
assert all(verify_subset_sum(values, 23, list(solution)) for solution in solutions)
assert solve_subset_sum([5, 10], 1) == []
assert solve_subset_sum([], 0) == [()]
# 삼각형 두 개를 이은 그래프: 크기 3 덮개는 없고 4는 있다
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (4, 5)]
assert not verify_vertex_cover(edges, {1, 2, 4}, 3)
assert verify_vertex_cover(edges, {0, 1, 3, 4}, 4)
assert not any(verify_vertex_cover(edges, set(cover), 3) for cover in combinations(range(6), 3))
print("ok")근사 알고리즘
"""근사 알고리즘: 정점 덮개 2-근사. 안 덮인 간선을 만나면 양 끝을 모두 넣는다.
시간: 근사 O(V + E), 비교용 최적 풀이 O(2^V · E)
공간: O(V)
"""
from itertools import combinations
def is_vertex_cover(edges: list[tuple[int, int]], cover: set[int]) -> bool:
"""모든 간선이 cover의 정점에 닿는가."""
return all(left in cover or right in cover for left, right in edges)
def approximate_vertex_cover(edges: list[tuple[int, int]]) -> tuple[list[tuple[int, int]], set[int]]:
"""고른 간선(극대 매칭)과 덮개를 돌려준다. 덮개 크기 = 고른 간선 수 × 2 ≤ 최적 × 2."""
cover: set[int] = set()
matching: list[tuple[int, int]] = []
for left, right in edges:
if left in cover or right in cover:
continue
matching.append((left, right))
cover.update((left, right))
return matching, cover
def minimum_vertex_cover(node_count: int, edges: list[tuple[int, int]]) -> set[int]:
"""작은 그래프 검산용: 크기 순으로 모든 정점 부분집합을 시험한다."""
for size in range(node_count + 1):
for nodes in combinations(range(node_count), size):
if is_vertex_cover(edges, set(nodes)):
return set(nodes)
return set(range(node_count))
if __name__ == "__main__":
# 노트의 그래프: 근사 6개, 최적 3개
tree = [(0, 1), (0, 2), (0, 3), (1, 4), (2, 5), (3, 6)]
matching, cover = approximate_vertex_cover(tree)
assert matching == [(0, 1), (2, 5), (3, 6)]
assert len(cover) == 6
assert minimum_vertex_cover(7, tree) == {1, 2, 3}
# 2 × 3 격자
grid = [(0, 1), (1, 2), (0, 3), (1, 4), (2, 5), (3, 4), (4, 5)]
matching, cover = approximate_vertex_cover(grid)
assert matching == [(0, 1), (2, 5), (3, 4)]
assert len(minimum_vertex_cover(6, grid)) == 3
# 별 모양: 근사 2개, 최적 1개로 비율이 정확히 2다
star = [(0, leaf) for leaf in range(1, 6)]
assert approximate_vertex_cover(star)[1] == {0, 1}
assert minimum_vertex_cover(6, star) == {0}
# 어떤 그래프든 근사 결과는 덮개이고, 최적의 두 배를 넘지 않는다
for edges, count in [(tree, 7), (grid, 6), (star, 6)]:
cover = approximate_vertex_cover(edges)[1]
assert is_vertex_cover(edges, cover)
assert len(cover) <= 2 * len(minimum_vertex_cover(count, edges))
assert approximate_vertex_cover([]) == ([], set())
print("ok")