동적 계획법 안내서 · 6/6

실무 활용

동적 계획법은 코딩 테스트에만 나오는 주제가 아닙니다. 매일 쓰는 많은 도구가 이름만 다를 뿐 안쪽에서 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 버그 대부분은 불완전한 상태, 잘못된 반복 방향, 재귀 한도, 오버플로에서 나옵니다.

더 읽을거리

이 장에 대해 질문이 있나요?