두 개의 문자열 A, B가 주어졌을 때, A를 편집하여 B로 만들려고 한다. 수행할 수 있는 연산은 다음 3가지다. 이때 최소 편집 횟수를 구하시오.
- 삽입(Insert): 특정한 위치에 문자 하나를 삽입합니다.
- 삭제(Remove): 특정한 위치에 문자 하나를 삭제합니다.
- 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.
SATURDAY
에 대해서 초기화 과정을 거친다.S
를 만들기 위해서는 추가 연산이 한 번 필요하므로 1
이 된다.SA
를 만들기 위해서는 추가 연산이 한 번 필요하므로 2
이 된다.SAT
를 만들기 위해서는 추가 연산이 한 번 필요하므로 3
이 된다.SATURDAY
를 만들기 위해서는 추가 연산이 한 번 필요하므로 8
이 된다.SUNDAY
에 대해서도 마찬가지로 3번과 같은 초기화 과정을 거친다.i
, j
두 변수를 이용해서 앞에서 부터 비교하며 메모이제이션 한다.i
번째 문자와 문자열 B의 j
번째 문자가 같은 경우(i-1, j-1)
에서 그대로 가져온다.i
번째 문자와 문자열 B의 j
번째 문자가 다른 경우SU
와 SAT
사이의 편집거리는 S
와 SA
사이의 편집거리에 수정연산을 한 번 하면 된다. (e.g. U
를 T
로 변경하는 연산)SU
와 SAT
사이의 편집거리는 SU
와 SA
사이의 편집거리에 삽입연산을 한 번 하면 된다. (e.g. T
문자를 넣어주는 연산)SU
와 SAT
사이의 편집거리는 S
와 SAT
사이의 편집거리에 삭제연산을 한 번 하면 된다. (e.g. U
문자를 삭제하는 연산)(i, j)
에 저장한다.6. 가장 마지막 요소가 두 문자열 사이의 최소 편집 거리이다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
string left, right; cin >> left >> right;
int leftLen = left.length() + 1, rightLen = right.length() + 1;
vector<vector<int>> dist(leftLen, vector<int>(rightLen));
for (int i = 0; i < leftLen; ++i) dist[i][0] = i;
for (int i = 0; i < rightLen; ++i) dist[0][i] = i;
for (int i = 1; i < leftLen; ++i)
for (int j = 1; j < rightLen; ++j) {
// 두 문자가 같은 경우, 추가 연산이 필요하지 않으므로 (i-1, j-1)에서 가져온다.
if (left[i - 1] == right[j - 1]) dist[i][j] = dist[i - 1][j - 1];
// 두 문자가 다른 경우, (교체 | 추가 | 삭제) 세 연산 중 cost가 가장 적은 것을 기록한다.
else dist[i][j] = 1 + min(min(dist[i - 1][j - 1], dist[i - 1][j]), dist[i][j - 1]);
}
cout << dist[left.length()][right.length()] << '\n';
}
설명 5.2.1에서 SU와 SAT 사이의 편집거리는 S와 SA사이의 편집거리에 수정연산을 한 번 하면 된다. (e.g. U를 T로 변경하는 연산)인데 U를 T로 변경하여도 ST와 SAT가 되어서 다르지않나요?