[CSES] Edit Distance (Levenshtein distance algorithm)

https://cses.fi/problemset/task/1639

dp를 배울 때 본 적이 있는듯한 문제인데 못 풀었다.

문제는 두 문자열 s1, s2가 주어지고 가능한 연산이 다음과 같을 때,

• 문자 하나를 추가한다
• 문자 하나를 삭제한다.
• 문자 하나를 교체한다.

최소 연산 횟수(편집 거리)를 구하는 문제이다.

접근

먼저 탐욕법을 활용하여 어떤 특정 순서에서 어떤 연산을 하는 것이 가장 효율적인가를 판단할 수 있는지 생각해봤을 때, 불가능하다는 결론이 나온다.

DP 점화식을 어떻게 구성해야할지 고민해봤을 때 DP에서 자주 등장하는 패턴인 i번째까지의 최소 횟수를 계산해볼 수 있다고 생각했다.

그런데 이 문제는 i번째까지 최소 횟수라고 해서 이후에도 그게 최적의 결과일 거라 보장할 수 없다.

예시로 주어지는 MOVIE, LOVE를 봤을 때
첫번째 문자를 비교할 때, 문자를 추가하는 것과 대체하는 것 중 어떤 것이 더 최적의 연산이라는 것을 보장할 수 없다.

위 경우에는 뒤 문자열들의 차이를 계산해서 M -> L이 최적일 거라고 생각할 수 있지만

MOVIE, OLVIE 같은 경우는 뒤에 문자열을 단순히 차례대로 비교해서는 판단이 불가능하다.

레벤슈타인 거리 알고리즘 (Levenshtein distance algorithm)

이 문제는 레벤슈타인 거리 알고리즘을 그대로 사용하는 알고리즘이다.
두 문자열 사이의 편집 거리(연산이 필요한 횟수)를 구하는 알고리즘이다.

문자열 사이의 유사도를 판단할 때 사용되는 이론이다.

dp[i][j] 는 s1의 i번째까지와 s2의 j번째까지 문자열의 최소 편집 거리를 의미한다.

점화식은 다음과 같다.

• s1[i] == s2[j] 인 경우

dp[i][j] = dp[i-1][j-1]

• s1[i] != s2[j] 인 경우

 dp[i][j] = min(dp[i - 1][j - 1], //교체
 			min(dp[i - 1][j], //삭제
 			dp[i][j - 1]))  //추가
            + 1;

초기화는 다음과 같이 진행한다.

    for (int i = 0; i<= s1.size(); i++) {
        dp[i][0] = i; // Deleting all characters from s1
    }
    for(int j = 0; j <= s2.size(); j++) {
        dp[0][j] = j; // Inserting all characters from s2
    }

코드

int main() {
   ios::sync_with_stdio(false);
   cin.tie(NULL);

   string s1, s2;
   cin >> s1 >> s2;

   int dp[s1.size() + 1][s2.size() + 1];

   for (int i = 0; i<= s1.size(); i++) {
       dp[i][0] = i; // Deleting all characters from s1
   }
   for(int j = 0; j <= s2.size(); j++) {
       dp[0][j] = j; // Inserting all characters from s2
   }

   for (int i = 1; i <= s1.size(); i++) {
       for (int j = 1; j <= s2.size(); j++) {
           if (s1[i - 1] == s2[j - 1])
           {
               dp[i][j] = dp[i - 1][j - 1];
           }
           else
           {
               dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
           }
       }
   }

   cout << dp[s1.size()][s2.size()];
   return 0;
}

dp에서 어떤 두가지 요소를 비교하며 경우의 수를 계산할 때, 2차원 배열을 활용하면서 i번째와 j번째 요소까지의 어떤 결과값을 기록해나가는 방법이 있음을 알았다.

dp는 알고리즘을 모르면 난이도가 급격히 상승하는 경우가 많은 것 같다.