문자열 편집 거리 (Edit Distance)

1. 문제 설명

두 개의 문자열 A, B가 주어졌을 때, A를 B로 변환하는 데 필요한 최소 연산 횟수(편집 거리)를 구하는 문제이다.

사용할 수 있는 연산은 세 가지이다.

1. 삽입 (Insertion) → 원하는 위치에 문자 추가
2. 삭제 (Deletion) → 특정 위치의 문자 제거
3. 수정 (Replacement) → 특정 위치의 문자를 다른 문자로 변경

예제

A = "SABSBA"
B = "ABABSA"

가능한 연산 방법:

"SABSBA" → "ABSBSA" → "ABABSA"  (총 2번 수정)

편집 거리는 2가 된다.

---

2. 해결 방법 (DP)

1) DP 정의

• dp[i][j] = A의 처음 i개의 문자와 B의 처음 j개의 문자를 일치시키는 데 필요한 최소 편집 거리

---

2) 점화식

각 dp[i][j]는 마지막 문자(A[i-1], B[j-1])를 기준으로 결정된다.

1. 문자가 같은 경우 (A[i-1] == B[j-1])

   dp[i][j] = dp[i-1][j-1];  // 변환 없이 유지

2. 문자가 다른 경우 (A[i-1] != B[j-1])

   • 삽입 (Insertion) → dp[i][j-1] + 1
   • 삭제 (Deletion) → dp[i-1][j] + 1
   • 수정 (Replacement) → dp[i-1][j-1] + 1

   dp[i][j] = Math.min(
       dp[i][j-1] + 1,  // 삽입 (Insertion)
       dp[i-1][j] + 1,  // 삭제 (Deletion)
       dp[i-1][j-1] + 1 // 수정 (Replacement)
   );

---

3) 초기값 설정

for (int i = 0; i <= n; i++) dp[i][0] = i; // A를 B("")로 만들기 위해 삭제 연산 i번 필요
for (int j = 0; j <= m; j++) dp[0][j] = j; // ""(빈 문자열)을 B로 만들기 위해 삽입 연산 j번 필요

---

3. 코드 구현 (Java)

import java.util.*;

public class EditDistance {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String A = sc.next();
        String B = sc.next();
        
        int n = A.length();
        int m = B.length();
        
        int[][] dp = new int[n + 1][m + 1];

        // 초기값 설정
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;

        // DP 점화식 적용
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];  // 문자가 같으면 그대로 유지
                } else {
                    dp[i][j] = Math.min(
                        dp[i][j - 1] + 1,  // 삽입 (Insertion)
                        Math.min(dp[i - 1][j] + 1,  // 삭제 (Deletion)
                                 dp[i - 1][j - 1] + 1) // 수정 (Replacement)
                    );
                }
            }
        }

        System.out.println("최소 편집 거리: " + dp[n][m]);
        sc.close();
    }
}

---

4. 핵심 원리

1) 왜 대각선 (dp[i-1][j-1])이 수정(Replacement)인가?

• dp[i-1][j-1]은 이전까지의 최적 상태를 의미.
• 문자가 다르면 A[i-1]을 B[j-1]로 바꿔야 하므로, 수정(Replace) 연산을 추가 (+1).
• 따라서 점화식에 dp[i-1][j-1] + 1이 포함됨.

2) 삽입(Insertion)과 삭제(Deletion) 공식

• dp[i][j-1] + 1 → B의 j번째 문자를 추가해야 하므로, B의 j-1까지 변환한 후 삽입
• dp[i-1][j] + 1 → A의 i번째 문자를 삭제해야 하므로, A의 i-1까지 변환한 후 삭제

3) 편집 거리에서 삽입(Insertion)과 삭제(Deletion)의 동작 방식

1️⃣ 삽입(Insertion): dp[i][j-1] + 1

• 정의: A를 B로 변환할 때, B의 j번째 문자를 추가하는 연산
• 즉, B의 j-1번째까지는 이미 변환 완료된 상태에서 새로운 문자를 삽입하는 것!

예제 1: "abc" → "abcd" (삽입)

A = "abc"
B = "abcd"

연산 과정

1. "abc" → "abcd" ('d' 추가)

DP 테이블

  a b c d
a 0 1 2 3
b 1 0 1 2
c 2 1 0 1

dp[i][j-1]은 A가 B의 j-1번째까지 변환된 상태
B의 j번째 문자를 삽입하면 dp[i][j-1] + 1이 된다!

2️⃣ 삭제(Deletion): dp[i-1][j] + 1

• 정의: A를 B로 변환할 때, A의 i번째 문자를 삭제하는 연산
• 즉, A의 i-1번째까지는 이미 변환 완료된 상태에서 A의 i번째 문자를 삭제하는 것!

예제 2: "abcd" → "abc" (삭제)

A = "abcd"
B = "abc"

연산 과정

1. "abcd" → "abc" ('d' 삭제)

DP 테이블

  a b c 
a 0 1 2 
b 1 0 1 
c 2 1 0
d 3 2 1   <-- "d"를 삭제해야 하므로, dp[i-1][j] + 1

dp[i-1][j]은 A의 i-1번째까지 변환된 상태
A의 i번째 문자를 삭제하면 dp[i-1][j] + 1이 된다!

4) 삽입과 삭제의 직관적인 이해

• 삽입(Insertion) → "B에 새로운 문자를 추가하는 연산"
• 삭제(Deletion) → "A의 특정 문자를 제거하는 연산"
• 각각 기존 최적 상태에서 한 번의 연산(+1)을 추가하는 개념

---

5. 예제 테스트

입력

SABSBA
ABABSA

출력

최소 편집 거리: 3

이 경우, "SABSBA"를 "ABABSA"로 변환하는 최소 연산 횟수는 3이다.

---

6. 시간 복잡도

• O(n × m) (이중 루프 사용)
• 문자열 길이가 길어도 DP를 사용하면 효율적으로 해결 가능!

---

7. 결론

✔ 문자열 편집 거리 문제는 동적 프로그래밍(DP)으로 해결 가능!
✔ 편집 거리 점화식을 올바르게 이해하면 최적의 알고리즘을 설계할 수 있다.
✔ 초기값 설정(dp[i][0] = i, dp[0][j] = j)을 통해 삭제/삽입 연산을 고려해야 한다.
✔ 시간 복잡도 O(n × m)으로 효율적으로 해결 가능하다.