C++로 두 문자열 간 최소 편집 거리(레벤슈타인 거리) 구하기

문제 개요

두 단어 S와 T가 주어졌을 때, S를 T로 변환하는 데 필요한 최소 연산 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음 세 가지입니다.

• 문자 삽입(insert)
• 문자 삭제(delete)
• 문자 교체(replace)

예를 들어 입력 문자열이 "evaluate"와 "fluctuate"라면 필요한 최소 연산 횟수는 5입니다. 이 값은 일반적으로 레벤슈타인 거리(Levenshtein Distance)라고 불리며, 동적 계획법(Dynamic Programming)을 이용하면 효율적으로 구할 수 있습니다.

풀이 접근 방식

핵심 아이디어는 dp[i][j]를 "s의 앞 i개 문자를 t의 앞 j개 문자로 변환할 때 필요한 최소 연산 횟수"로 정의하는 것입니다. 전체 알고리즘은 다음과 같습니다.

• n := s의 길이, m := t의 길이

• (n+1) × (m+1) 크기의 2차원 배열 dp 생성

• i를 0부터 n까지 반복:

  • dp[i] := m+1 크기의 새 배열 할당

  • j를 0부터 m까지 반복:

    • dp[i][j] := 0으로 초기화

    • i = 0이면 dp[i][j] = j (빈 문자열에 j개의 문자를 삽입하는 경우)

    • 그렇지 않고 j = 0이면 dp[i][j] = i (i개의 문자를 모두 삭제하는 경우)

• s := 공백 + s, t := 공백 + t (인덱스를 1부터 사용하기 위해 앞에 공백 추가)

• i를 1부터 n까지, j를 1부터 m까지 반복:

  • s[i] ≠ t[j]라면 dp[i][j] := 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    (각각 삭제, 삽입, 교체에 해당)

  • s[i] = t[j]라면 dp[i][j] := dp[i-1][j-1] (연산 없이 이전 상태 그대로)

• dp[n][m] 반환

구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minDistance(string s, string t) {
      int n = s.size();
      int m =t.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;
         }
      }
      s = " " + s;
      t = " " + t;
      for(int i =1;i<=n;i++){
         for(int j = 1;j<=m;j++){
            if(s[i] !=t[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];
   }
};
main(){
   Solution ob;
   cout << (ob.minDistance("fluctuate", "evaluate"));
}

입력

"fluctuate"
"evaluate"

출력

5

정리

이 알고리즘의 시간 복잡도는 O(n × m), 공간 복잡도 역시 O(n × m)입니다. 두 문자열의 유사도를 수치화하는 대표적인 방법으로, 맞춤법 검사기, DNA 서열 분석, 자연어 처리 등 다양한 분야에서 활용됩니다. 만약 메모리 사용량을 줄이고 싶다면 롤링 배열(Rolling Array) 기법을 적용해 공간 복잡도를 O(m)까지 줄일 수 있습니다.