알고리즘 - 최소 편집 거리(Minimum Edit Distance)

문자열 S를 다른 문자열 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수를 구하는 문제.

 

1회의 연산에는 삽입(insert), 삭제(delete), 대체(substitute)중 한 가지만 할 수 있다.

 

문자열 S = strong

문자열 T = stone

S를 T로 변환하기 위해서는 총 4회의 편집 연산이 필요하다.

 

s t    r o n g

s t o      n  e

1. o 삽입

2. r 삭제

3. o 삭제

4. g -> e 대체

 

총 4회의 편집 연산이 필요하다.