C++로 구현하는 편집 거리(Edit Distance) 알고리즘

편집 거리(Edit Distance)란?

두 개의 문자열 word1과 word2가 주어졌을 때, word1을 word2로 변환하는 데 필요한 최소 연산 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음 세 가지입니다.

삽입(Insert) : 새로운 문자 하나를 추가
삭제(Delete) : 기존 문자 하나를 제거
교체(Replace) : 기존 문자를 다른 문자로 변경

예를 들어 입력 문자열이 "evaluate"와 "fluctuate"라면, 두 문자열을 일치시키기 위해 필요한 최소 연산 횟수는 5입니다.

해결 접근 방식

이 문제는 대표적인 동적 계획법(Dynamic Programming) 문제로, 다음과 같은 순서로 해결할 수 있습니다.

n := w1의 길이, m := w2의 길이로 설정
크기가 (n + 1) × (m + 1)인 2차원 배열 dp를 생성하고 0으로 초기화
경계 조건 설정 : i = 0이면 dp[i][j] = j, j = 0이면 dp[i][j] = i
w1과 w2 앞에 공백 한 칸을 붙여 인덱스를 1부터 시작하도록 조정
i를 1부터 n까지, j를 1부터 m까지 반복하며 다음을 수행 :
- w1[i] ≠ w2[j]이면 dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
- w1[i] == w2[j]이면 dp[i][j] = dp[i-1][j-1]
최종적으로 dp[n][m] 값을 반환

점화식의 의미

dp[i][j]는 "w1의 앞 i개 문자를 w2의 앞 j개 문자로 바꾸는 데 필요한 최소 연산 횟수"를 의미합니다. 비교하는 두 문자가 같다면 추가 연산 없이 대각선 값(dp[i-1][j-1])을 그대로 가져오고, 다르다면 삽입·삭제·교체 세 가지 경우 중 최솟값에 1을 더한 값이 됩니다.

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minDistance(string w1, string w2) {
        int n = w1.size();
        int m = w2.size();
        int** dp = new int*[n+1];
        for(int i = 0; i <= n; i++){
            dp[i] = new int[m+1];
            for(int j = 0; j <= m; j++){
                dp[i][j] = 0;
                if(i == 0) dp[i][j] = j;
                else if(j == 0) dp[i][j] = i;
            }
        }
        w1 = " " + w1;
        w2 = " " + w2;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(w1[i] != w2[j]){
                    dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
                } else {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[n][m];
    }
};
int main(){
    Solution ob;
    cout << (ob.minDistance("fluctuate", "evaluate"));
}

실행 결과

입력

"fluctuate"
"evaluate"