정석 2D DP: 부분 문제의 격자

"문제가 문자열 두 개나 아이템과 예산처럼 두 축을 한꺼번에 다루기 시작하면, 상태도 숫자 두 개짜리 격자가 돼. 편집 거리와 LCS는 맞춤법 제안, diff, DNA 서열 비교를 떠받치는 기초 일꾼이야. 제품 전체가 이 표 하나로 돌아간다는 뜻은 아니지만, 이 격자 없이는 서지 못할 물건이 수두룩해."

상태의 두 차원

2D DP는 부분 문제가 숫자 쌍으로 식별되는 DP야. 그래서 테이블이 격자가 되지. 가장 흔한 모양은 수열 두 개를 놓고 dp[i][j]가 'A의 첫 i개와 B의 첫 j개'에 관한 질문에 답하는 꼴이야. dp[i][w]를 '예산 w 안에서 첫 i개 아이템을 쓴 결과'로 두는 꼴도 있고. 각 칸은 위, 왼쪽, 대각선 같은 이웃 값들로 계산되고, 그 이웃들이 필요한 시점에 준비돼 있도록 격자를 보통 행 단위로 채워.

편집 거리: 정석 2D DP

두 문자열 사이의 편집 거리, 즉 Levenshtein 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 최소한의 단일 문자 삽입, 삭제, 치환 횟수야. dp[i][j]를 A의 첫 i글자와 B의 첫 j글자 사이의 편집 거리로 정의해. 그러면 점화식이 결정문처럼 읽혀. 현재 문자가 일치하면 편집이 필요 없으니 dp[i][j] = dp[i-1][j-1]. 일치하지 않으면 세 가지 선택, 즉 삭제(dp[i-1][j]), 삽입(dp[i][j-1]), 치환(dp[i-1][j-1]) 가운데 최소에 1을 더해. 이웃 셋에 min 하나. 문자열을 빈 문자열로 바꾸는 비용은 그 길이라는 base case가 첫 행과 첫 열을 채워 주고.

2D DP는 상태를 쌍 (i, j)로 인덱싱해. 보통 두 수열의 위치거나 (인덱스, 용량)이야. 각 칸은 위, 왼쪽, 대각선 같은 이웃 몇 개에 의존하고, 격자는 의존성 순서대로 채워. 정석 예시가 편집 거리와 LCS고, diff와 맞춤법 검사와 DNA 정렬이 그 위에 서 있어.

편집 거리가 떠받치는 세상

편집 거리와 LCS는 맞춤법 제안, 퍼지 매칭, diff, 생물정보학의 서열 비교를 이해하는 데 중요한 기초야. 다만 실제 제품은 성능과 품질을 위해 Myers diff, 토큰화, 휴리스틱, 도메인별 점수 같은 기법을 함께 써. 0/1 배낭도 마찬가지로 예산과 자원 할당을 모델링하는 출발점이지, 모든 현실 시스템 뒤에 숨은 단일 엔진은 아니야.

피파의 고백

편집 거리 격자가 나한텐 그냥 임의의 표처럼 느껴졌어. 아빠가 칸 하나가 뭘 뜻하는지 라벨을 붙이게 하기 전까진. dp[3][2]는 'A의 첫 3글자를 B의 첫 2글자로 바꾸는 비용'이야. 칸마다 문장이 생기니까 세 갈래 min이 공식이기를 멈추고 명백한 세 가지 선택이 됐어. 삭제, 삽입, 치환. 그 뒤로 모든 2D DP를 풀어 준 트릭은 하나야. dp[i][j]가 정확히 뭘 나타내는지 평범한 말로 할 수 있을 때까지 점화식 쓰기를 거부하는 것.

Code

편집 거리: 정석 2D DP·python

# 편집 거리 (Levenshtein): 최소 삽입/삭제/치환.
# dp[i][j] = A[:i] 랑 B[:j] 사이 편집 거리.
def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i              # base: A[:i] 를 '' 로 -> i 삭제
    for j in range(n + 1):
        dp[0][j] = j              # base: '' 를 B[:j] 로 -> j 삽입
    for i in range(1, m + 1):
        for j in range(1, n + 1):       # 행별로 채움 (의존성 준비됨)
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]        # 일치: 편집 없음
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j],    # A 에서 삭제
                    dp[i][j-1],    # A 에 삽입
                    dp[i-1][j-1],  # 치환
                )
    return dp[m][n]

print(edit_distance("kitten", "sitting"))   # 3  (k->s, e->i, +g)
# 각 칸 = '이 A 접두사를 이 B 접두사로 변환하는 비용'.
# 이 정확한 DP 가 맞춤법 검사 순위를 굴리고 diff/DNA 정렬이랑 친척.

Exercise

A='ab'와 B='ac'로 편집 거리 테이블의 첫 두 행을 만들어 봐. 일치하면 대각선, 불일치면 1 + 세 이웃의 min이라는 규칙으로 dp[0][*]와 dp[1][*]를 채워. dp[1][1]이 뭘 나타내고 왜 그 값인지 말로 설명해. 그다음 편집 거리나 그 사촌인 LCS 위에 서 있는 진짜 시스템 두 개를 대 봐.

Hint

dp[0] = [0, 1, 2](''를 'ac'의 접두사들로 만드는 비용). dp[1][0] = 1. dp[1][1]은 A[0]='a'와 B[0]='a'가 일치하니 대각선 dp[0][0] = 0을 그대로 받아서 0이야. 'a'를 'a'로 바꾸는 데 비용이 들지 않는다는 뜻이지. 진짜 시스템은 맞춤법 검사기(제안을 편집 거리로 순위 매김), diff와 버전 관리, DNA 정렬(최장 공통 부분수열).

상태의 두 차원

편집 거리: 정석 2D DP

편집 거리가 떠받치는 세상

피파의 고백

Code

External links

Exercise

Progress

댓글 0