[고급 알고리즘] Dynamic Programming: Edit Distance

1. Edit Distance

• 두 문자열 간의 최소 편집 거리를 계산하는 문제입니다.
• 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 연산의 수를 의미합니다.

 

연산

• 삽입: 문자 삽입
• 삭제: 문자 삭제
• 교체: 한 문자를 다른 문자로 교체

DP 테이블 정의

dp[i][j]

• i~j까지 최소 편집 연산 수

 

점화식

A[i-1]  == B[j-1]

• dp[i][j] = dp[i-1][j-1]
• 문자가 같으므로 편집 필요 없음

 

A[i-1]  != B[j-1]

• 삽입, 삭제, 교체 중, 최소값을 선택
• 삽입
  • A에 문자를 삽입하여 B와 같아지게 함 
  • dp[i][j-1] + 1
• 삭제
  • A에 문자를 삭제하여 B와 같아지게 함 
  • dp[i-1][j] + 1
• 교체
  • A의 문자를 다른 문자로 교체하여 B와 같아지게 함
  • dp[i-1][j-1] + 1

 

 

출처

• Wiki - Edit Distance