편집 거리(Edit Distance) 알고리즘: 두 문자열 간 최소 편집 횟수 구하기

편집 거리란 무엇인가?

두 개의 문자열이 주어졌을 때, 첫 번째 문자열은 소스(source) 문자열, 두 번째 문자열은 타겟(target) 문자열이라고 합니다. 편집 거리(Edit Distance) 알고리즘은 소스 문자열을 타겟 문자열로 변환하는 데 필요한 최소 편집 횟수를 구하는 문제입니다.

여기서 말하는 '편집'은 다음 세 가지 연산 중 하나를 의미합니다.

삽입(Insert) — 새로운 문자를 추가
삭제(Delete) — 기존 문자를 제거
수정(Modify) — 기존 문자를 다른 문자로 변경

입력과 출력

프로그램은 비교할 두 문자열을 입력받고, 변환에 필요한 총 편집 횟수를 출력합니다.

Input:
string 1: Programming
string 2: Programs

Output:
Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

알고리즘

이 문제는 재귀 호출을 통해 해결할 수 있습니다. 함수 시그니처는 다음과 같습니다.

editCount(initStr, finalStr, initLen, finalLen)

입력 — 초기 문자열과 최종 문자열, 그리고 각각의 길이
출력 — initStr을 finalStr로 만들기 위해 필요한 편집 횟수

동작 원리

초기 문자열의 길이가 0이면, 최종 문자열의 모든 문자를 삽입해야 하므로 finalLen을 그대로 반환합니다.
최종 문자열의 길이가 0이면, 초기 문자열의 모든 문자를 삭제해야 하므로 initLen을 그대로 반환합니다.
두 문자열의 마지막 문자가 서로 같다면, 해당 문자는 편집이 필요 없으므로 앞부분에 대해 재귀 호출합니다.
마지막 문자가 다르다면, 삽입·삭제·수정 세 가지 경우를 각각 재귀적으로 수행한 뒤 그중 최솟값에 1을 더해 반환합니다.

Begin
   if initLen = 0, then
      return finalLen
   if finalLen = 0, then
      return initLen

   if initStr[initLen - 1] = finalStr[finalLen - 1], then
      return editCount(initStr, finalStr, initLen – 1, finalLen - 1)
   answer := 1 + min of (editCount(initStr, finalStr, initLen, finalLen - 1)),
      (editCount(initStr, finalStr, initLen – 1, finalLen),
      (editCount(initStr, finalStr, initLen – 1, finalLen - 1)
   return answer
End

C++ 구현 예제

위 알고리즘을 C++로 구현한 전체 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

int min(int x, int y, int z) {     //세 수 중 가장 작은 값 찾기
   if(x < y) {
      if(x < z)
         return x;
      else
         return z;
   }else {
      if(y < z)
         return y;
      else
         return z;
   }
}

int editCount(string initStr, string finalStr, int initLen, int finalLen) {
   if (initLen == 0)     //초기 문자열이 비어 있으면, 최종 문자열의 모든 문자를 삽입
      return finalLen;

   if (finalLen == 0)     //최종 문자열이 비어 있으면, 초기 문자열의 모든 문자를 삭제
      return initLen;

   //마지막 문자가 일치하면, 앞부분에 대해 재귀적으로 검사
   if (initStr[initLen-1] == finalStr[finalLen-1])
      return editCount(initStr, finalStr, initLen-1, finalLen-1);

   //마지막 문자가 일치하지 않으면, 삽입·삭제·수정 연산을 재귀적으로 수행
   return 1 + min (
      editCount(initStr, finalStr, initLen, finalLen-1),  // insert (삽입)
      editCount(initStr, finalStr, initLen-1, finalLen),  // delete (삭제)
      editCount(initStr, finalStr, initLen-1, finalLen-1)  // update (수정)
   );
}

int main() {
   string initStr;
   string finalStr;

   cout << "Enter the initial string: "; cin >> initStr;
   cout << "Enter the final string: "; cin >> finalStr;
   cout << "The number of changes required to convert " << initStr << " to " << finalStr;
   cout << " is " << editCount(initStr, finalStr, initStr.size(), finalStr.size()) << endl;
}

실행 결과

Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

시간 복잡도 참고

위 재귀 방식은 직관적이지만, 같은 부분 문제를 반복해서 계산하기 때문에 최악의 경우 시간 복잡도가 지수적으로 증가할 수 있습니다. 실무에서는 동적 계획법(Dynamic Programming)을 활용해 부분 문제의 결과를 테이블에 저장하면 O(m×n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 여기서 m과 n은 각각 두 문자열의 길이입니다.