동적 계획법은 코딩 테스트에만 나오는 주제가 아닙니다. 매일 쓰는 많은 도구가 이름만 다를 뿐 안쪽에서 DP를 돌립니다. 이 장에서는 그런 곳들을 훑어보고, 작은 실무형 예제 두 개를 살펴본 뒤, DP 코드를 망가뜨리는 흔한 실수를 정리합니다.
DP가 쓰이는 곳
- diff와 버전 관리: 두 파일을 비교하는 일은 LCS, 곧 최단 편집 스크립트 문제입니다. GNU diff와 Git의 기본 diff는 차이가
D개일 때 O(ND) 시간에 도는 Myers 알고리즘을 씁니다. - 맞춤법 검사와 퍼지 검색: 편집 거리(레벤슈타인 거리)로 검색어와 몇 글자 차이 나는지를 재어 후보 단어의 순위를 매깁니다.
- 생물정보학: Needleman-Wunsch(전역 정렬)와 Smith-Waterman(지역 정렬)은 점수를 매긴 편집 거리 표로 DNA나 단백질 서열을 정렬합니다.
- 음성, 텍스트, 신호: 비터비(Viterbi) 알고리즘은 은닉 마르코프 모델에서 가장 그럴듯한 숨은 상태의 열을 찾습니다. 음성 인식, 품사 태깅, 디지털 통신의 컨볼루션 부호 복호에 쓰입니다.
- 네트워크: RIP 같은 거리 벡터 라우팅 프로토콜은 벨먼-포드 점화식에 기반합니다.
- 데이터베이스: 쿼리 플래너는 테이블 부분집합에 대한 DP로 조인 순서를 고릅니다. IBM System R에서 시작된 방식이며, PostgreSQL은 조인하는 테이블이 많아지면 이 탐색 대신 유전 알고리즘 최적화기(GEQO)로 바꿉니다.
- 조판: TeX의 Knuth-Plass 줄 나눔은 문단 전체의 "나쁨(badness)" 합이 최소가 되도록 DP로 줄바꿈 위치를 고릅니다.
- 계획과 자원 배분: 강화 학습의 가치 반복은 벨먼 방정식을 반복 적용하며, 예산 편성이나 화물 적재는 배낭 문제의 변형입니다.
예제: 가장 가까운 명령어 추천
명령줄 도구는 사용자가 명령 이름을 잘못 입력했을 때 고쳐 쓸 이름을 추천할 수 있습니다. 한 행만 굴리는 편집 거리로 충분합니다.
def edit_distance(s: str, t: str) -> int:
prev = list(range(len(t) + 1))
for i, a in enumerate(s, start=1):
cur = [i] + [0] * len(t)
for j, b in enumerate(t, start=1):
cur[j] = prev[j - 1] if a == b else 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[-1]
def suggest(word: str, commands: list[str], max_distance: int = 2) -> str | None:
best = min(commands, key=lambda c: edit_distance(word, c))
return best if edit_distance(word, best) <= max_distance else None
print(suggest("stauts", ["status", "commit", "push", "stash"])) # status
print(suggest("deploy", ["status", "commit", "push", "stash"])) # None
Python 표준 라이브러리의 difflib.get_close_matches도 비슷한 일을 하지만, 최소 편집 거리가 아니라 SequenceMatcher의 유사도 비율로 순위를 매깁니다.
예제: 작은 모델에서 비터비
모니터링 시스템이 응답 시간을 "fast" 또는 "slow"로만 관찰하고, 각 시점에 서버가 "ok"였는지 "degraded"였는지 추정하려고 합니다. 비터비는 시점 t의 각 상태마다 그 상태에서 끝나는 가장 좋은 경로의 확률과 직전 상태를 가리키는 포인터를 저장합니다.
def viterbi(observations, states, start, trans, emit):
best = [{s: (start[s] * emit[s][observations[0]], None) for s in states}]
for obs in observations[1:]:
prev = best[-1]
best.append({
s: max((prev[p][0] * trans[p][s] * emit[s][obs], p) for p in states)
for s in states
})
state = max(states, key=lambda s: best[-1][s][0])
path = [state]
for layer in reversed(best[1:]):
state = layer[state][1]
path.append(state)
return path[::-1]
states = ("ok", "degraded")
start = {"ok": 0.9, "degraded": 0.1}
trans = {"ok": {"ok": 0.95, "degraded": 0.05}, "degraded": {"ok": 0.2, "degraded": 0.8}}
emit = {"ok": {"fast": 0.9, "slow": 0.1}, "degraded": {"fast": 0.3, "slow": 0.7}}
print(viterbi(["fast", "fast", "slow", "slow", "slow", "fast"], states, start, trans, emit))
# ['ok', 'ok', 'degraded', 'degraded', 'degraded', 'degraded']
실제 구현은 작은 확률을 여러 번 곱하면 0으로 언더플로가 나기 때문에 확률을 곱하는 대신 로그 확률을 더합니다.
흔한 실수
- 잘못된 상태: 답이 상태에 기록되지 않은 정보(남은 용량, 직전 선택 등)에 따라 달라지면, 캐시는 다른 상황의 답을 돌려줍니다.
- 반복 방향: 한 행 0/1 배낭에서 용량을 작은 쪽부터 돌면 소리 없이 무한 배낭이 됩니다.
- 재귀 깊이: Python의 기본 재귀 한도는 약 1000단계이므로 긴 사슬은 상향식 반복문으로 바꿉니다.
- 오버플로: 경우의 수는 빠르게 커집니다. C++과 Java에서는 64비트 정수나 나머지 연산을 씁니다.
- 무한히 커지는 캐시:
functools.cache는 항목을 지우지 않으므로 오래 도는 서비스에서는 끝없이 커질 수 있습니다. lru_cache(maxsize=...)를 쓰거나 직접 비웁니다. - 해시할 수 없는 인자: 캐시하는 함수의 인자는 해시 가능해야 하므로 리스트 대신 튜플이나 문자열을 넘깁니다.
from functools import cache, lru_cache
@cache
def total(items: tuple[int, ...]) -> int:
return sum(items)
try:
total([1, 2, 3])
except TypeError as error:
print("lists cannot be cache keys:", error)
print(total((1, 2, 3))) # 6
@lru_cache(maxsize=1024) # 가장 오래 쓰지 않은 항목부터 지움
def score(word: str) -> int:
return sum(map(ord, word))
score.cache_clear() # 직접 모두 비울 수도 있음
정리
- DP는 diff, 맞춤법 검사, 서열 정렬, 음성 복호, 라우팅, 쿼리 계획, 조판을 움직입니다.
- 실무 코드는 교과서 점화식에 로그 확률, 크기 제한 캐시, 롤링 배열 같은 장치를 더합니다.
- DP 버그 대부분은 불완전한 상태, 잘못된 반복 방향, 재귀 한도, 오버플로에서 나옵니다.
더 읽을거리
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.