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

"문제가 두 가지를 한 번에 다룰 때 — 문자열 둘, 또는 아이템-더하기-예산 — 상태가 숫자 둘이 필요하고, DP 테이블이 격자가 돼. 이 2D DP 가 맞춤법 검사, DNA 정렬, 파일 diff 뒤의 일꾼이야."

상태의 두 차원

2D 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] (편집 불필요); 아니면 1 + min 세 선택 — 삭제 (dp[i-1][j]), 삽입 (dp[i][j-1]), 치환 (dp[i-1][j-1]). 이웃 셋, min 하나. base case (문자열을 빈 문자열로 바꾸는 데 그 길이만큼 비용) 가 첫 행이랑 열을 씨앗.

2D DP 는 상태를 쌍 (i, j) 로 인덱싱해 — 보통 두 수열 위치, 또는 (인덱스, 용량). 각 칸이 이웃 몇 개 (위 / 왼쪽 / 대각선) 에 의존; 격자를 의존성 순서로 채움. 편집 거리랑 LCS 가 정석 예, diff, 맞춤법 검사, DNA 정렬을 굴려.

2D DP 가 세상을 굴리는 곳

이건 학술 장난감이 아니야. 편집 거리가 맞춤법 검사기 ('혹시 …?' 가 후보를 편집 거리로 순위) 랑 퍼지 매칭을 굴려. 최장 공통 부분수열이 diff 랑 버전 관리 (두 파일 사이 뭐 바뀌었는지 찾기) 랑 생물정보학의 DNA/단백질 서열 정렬의 엔진이야. 0/1 배낭 (무게 한계 안 최대 값, 각 아이템 취하거나 안 함) 이 예산, 자원 할당, 화물 적재를 모델링해. 연습처럼 보이는 2D 테이블이, production 에선 네 에디터가 파일을 diff 하는 법이고 유전학자가 게놈을 비교하는 법이야.

피파의 고백

편집 거리 격자가 임의로 느껴졌어, 아빠가 한 칸이 뭘 뜻하는지 라벨 붙이게 하기 전까진: 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. dp[1][1]=0 은 'a'→'a' 가 비용 0 이란 뜻. 진짜 시스템: 맞춤법 검사기 (제안을 편집 거리로 순위) 랑 diff/버전 관리 + DNA 정렬 (최장 공통 부분수열).

상태의 두 차원

편집 거리: 정석 2D DP

2D DP 가 세상을 굴리는 곳

피파의 고백

Code

External links

Exercise

Progress

댓글 0