Chap 5-3. 편집거리 (Edit Distance)
[편집거리 (Edit Distance)] = 삽입 (insert), 삭제 (delete), 대체 (substitute) 연산을 사용하여 스트링(문자열) S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 즉, 3개의 연산(삽입, 삭제, 대체)을 통해 다른 문자열로 변환이 가능하다. [예시 strong -> stone] strong을 stone으로 바꿔보자 2가지 방법이 가능하다. 방법 1 ) 순서대로 s, t는 그대로 두고 o를 삽입하고 r, o를 삭제한다. n은 그대로 두고 g를 e로 바꾼다. ⇒ 총 4회의 편집 연산을 했다. 방법 2) ‘s’와 ‘t’는 그대로 사용한 후, ‘r’을 삭제하고, ‘o’와 ‘n’을 그대로 사용한 후, ‘g’를 ‘e’로 대체하여, 총 2회의 편집..
