Edit Distance (1) 썸네일형 리스트형 편집 거리(Edit Distance) 알고리즘 다음 문제를 생각해보자. 문자열 a와 b가 있다. 여기서 각 문자열의 임의 위치를 삭제하거나 다른 문자로 교체, 그리고 임의의 문자를 삽입하는 행위의 비용을 1이라고 할 때 a와 b를 같은 문자열로 만드는 최소 비용을 구하라. 예를 들어 "abc"와 "abd"가 있을 때 세 번째 글자를 동일하게 만들면 되므로 편집 거리는 1이다. "ABCD"와 "ABd"는 'D'를 삭제하고 'C'를 'd'로 바꾸면 되므로 편집 거리는 2이다. 혹은 "ABd"에서 'd'를 'C'로 바꾸고 'D'를 추가해도 된다. 이 문제는 2차원 dp로 풀 수 있음이 널리 알려져 있다. 어떻게 dp로 풀 수 있는지 같이 살펴보도록 하자. 우선 단어를 하나 이해해야 한다. align: 보통 맞추다 혹은 정렬(sort가 아님을 유의)이라고 .. 이전 1 다음
