편집거리 문제

편집 거리

편집 거리(레벤슈타인 거리)는 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 작업 수를 의미합니다. 여기서 편집 작업은 다음 세 가지를 포함합니다:

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

---

알고리즘 작동 원리

이 문제는 다이나믹 프로그래밍 알고리즘을 사용하여 해결할 수 있습니다. 큰 문제를 작은 하위 문제로 나누어 풀고, 그 결과를 재사용하여 효율적으로 답을 구합니다.

---

어떻게 작은 문제로 쪼개어 풀 수 있을까?

예를 들어, ABC를 QWER로 변환하는 편집 거리를 구한다면, 다음과 같은 세 가지 연산을 고려할 수 있습니다:

• 삽입: QWE에 R을 삽입하는 경우
  → ABC와 QWE의 편집 거리 + 1
• 삭제: ABC에서 C를 삭제하는 경우
  → AB와 QWER의 편집 거리 + 1
• 교체: ABC의 C를 R로 교체하는 경우
  → AB와 QWE의 편집 거리 + 1

이처럼, 더 작은 문자열 쌍의 편집 거리를 구해 나가며 문제를 해결할 수 있어 다이나믹 프로그래밍에 적합합니다.

---

DP 테이블 생성 및 초기화

편집 거리를 구하기 위해 2차원 DP 테이블을 사용합니다.

• dp[i][j]: str1의 첫 i개 문자와 str2의 첫 j개 문자의 편집 거리를 의미합니다.

초기화:

• dp[i][0] = i: str1의 첫 i개 문자를 빈 문자열로 변환하는 데 필요한 삭제 연산 수.
• dp[0][j] = j: 빈 문자열을 str2의 첫 j개 문자로 변환하는 데 필요한 삽입 연산 수.

초기 DP 테이블 예시:

       ""  s  a  t  u  r  d  a  y
""   [0, 1, 2, 3, 4, 5, 6, 7, 8]
s    [1, 0, 0, 0, 0, 0, 0, 0, 0]
u    [2, 0, 0, 0, 0, 0, 0, 0, 0]
n    [3, 0, 0, 0, 0, 0, 0, 0, 0]
d    [4, 0, 0, 0, 0, 0, 0, 0, 0]
a    [5, 0, 0, 0, 0, 0, 0, 0, 0]
y    [6, 0, 0, 0, 0, 0, 0, 0, 0]

---

종합 점화식

DP 테이블을 채우기 위한 점화식은 다음과 같습니다:

if str1[i-1] == str2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

• 두 문자가 같으면(str1[i-1] == str2[j-1]): 추가 연산 없이 이전 값을 그대로 사용합니다.
• 두 문자가 다르면: 삽입(dp[i][j-1]), 삭제(dp[i-1][j]), 교체(dp[i-1][j-1]) 중 최소 비용을 선택하고 1을 더합니다.

구현

static int editDist(String str1, String str2) {
        int n = str1.length();
        int m = str2.length();

        // 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
        int[][] dp = new int[n + 1][m + 1];

        // DP 테이블 초기 설정
        for (int i = 1; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= m; j++) {
            dp[0][j] = j;
        }

        // 최소 편집 거리 계산
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
                else { // 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                    dp[i][j] = 1 + Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1]));
                }
            }
        }

        return dp[n][m];
    }