알고리즘 :: 이것이 코딩 테스트다 :: DP :: Q36 :: 편집 거리

문제

두 개의 문자열 A, B가 주어졌을 때, A를 편집하여 B로 만들려고 한다. 수행할 수 있는 연산은 다음 3가지다. 이때 최소 편집 횟수를 구하시오.

1. 삽입(Insert): 특정한 위치에 문자 하나를 삽입합니다.
2. 삭제(Remove): 특정한 위치에 문자 하나를 삭제합니다.
3. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.

문제접근

• 이 문제는 직접 풀지 못했고 검색을 통해 구현할 수 있었다.
• 새로운 내용을 알게되어 정리하고자 한다.

편집 거리 알고리즘

• 편집 거리 알고리즘이란, 두 문자열의 유사도를 판단하는 알고리즘이다.
• 삽입, 삭제, 교체가 가능할 때 A 문자열을 B 문자열로 바꾸는 최소 횟수(최소 편집 거리)를 구하는 알고리즘이다.
• 외부 2차원 메모이제이션 배열에 수행 결과를 저장하고 이를 다음번에 이용하므로 DP 알고리즘을 기반으로 한다.
  

1. 문자열 A와 B를 입력받고 위와 같이 길이에 맞게끔 2차원 메모이제이션 배열을 생성한다.
2. 이때 문자가 아무것도 없는 널문자까지 포함해서 생각해줘서 열과 행에 한 칸씩을 더 만든다.
3. SATURDAY에 대해서 초기화 과정을 거친다.
   • 널문자에서 S를 만들기 위해서는 추가 연산이 한 번 필요하므로 1이 된다.
     널문자에서 SA를 만들기 위해서는 추가 연산이 한 번 필요하므로 2이 된다.
     널문자에서 SAT를 만들기 위해서는 추가 연산이 한 번 필요하므로 3이 된다.
     (...중략...)
     널문자에서 SATURDAY를 만들기 위해서는 추가 연산이 한 번 필요하므로 8이 된다.
4. SUNDAY에 대해서도 마찬가지로 3번과 같은 초기화 과정을 거친다.
   
5. 이제 두 문자열을 i, j 두 변수를 이용해서 앞에서 부터 비교하며 메모이제이션 한다.
   1. 문자열 A의 i번째 문자와 문자열 B의 j번째 문자가 같은 경우
      • 두 문자가 같다면 별다른 연산이 필요하지 않으므로 (i-1, j-1)에서 그대로 가져온다.
   2. 문자열 A의 i번째 문자와 문자열 B의 j번째 문자가 다른 경우
      1. A과정: SU와 SAT 사이의 편집거리는 S와 SA사이의 편집거리에 수정연산을 한 번 하면 된다. (e.g. U를 T로 변경하는 연산)
      2. B과정: SU와 SAT 사이의 편집거리는 SU와 SA사이의 편집거리에 삽입연산을 한 번 하면 된다. (e.g. T 문자를 넣어주는 연산)
      3. C과정: SU와 SAT 사이의 편집거리는 S와 SAT사이의 편집거리에 삭제연산을 한 번 하면 된다. (e.g. U 문자를 삭제하는 연산)
      4. 세 과정중에서 제일 적은 편집 거리를 (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';
}