문제 설명

Edit Distance - LeetCode

두 개의 문자열 word1과 word2가 주어질 때,
첫 번째 문자열을 두 번째 문자열로 변환하기 위한 최소 편집 횟수를 구하는 문제입니다.

✅ 편집 연산 (Operations)

  1. 삽입 (Insert) → 문자를 추가
  2. 삭제 (Delete) → 문자를 제거
  3. 변경 (Replace) → 문자를 다른 문자로 변경

✅ 제약 조건

  • 0 ≤ word1.length, word2.length ≤ 500
  • 최적화된 O(m × n) 알고리즘이 필요

해설

1️⃣ 재귀 (O(3^N)) → 비효율적

  • 모든 가능한 연산을 수행하여 최소 값을 찾음
  • 시간 복잡도 O(3^N) → 매우 비효율적
  • 사용하지 않음

2️⃣ 동적 계획법 (DP, O(m × n)) [추천]

✔ DP 테이블을 사용하여 중복 연산을 제거
✔ 점화식:

  • dp[i][j]: word1[0:i] → word2[0:j] 변환하는 최소 편집 거리

  • word1[i-1] == word2[j-1]이면 dp[i][j] = dp[i-1][j-1]

  • 다르면 삽입, 삭제, 변경 중 최소 연산 선택

    1
2
3
4
5

    dp[i][j] = min(
    dp[i-1][j] + 1,  # 삭제 (Delete)
    dp[i][j-1] + 1,  # 삽입 (Insert)
    dp[i-1][j-1] + 1 # 변경 (Replace)
)

✔ 시간 복잡도: O(m × n)
✔ 공간 복잡도: O(m × n) → O(min(m, n))로 최적화 가능

예를 들어, word1 = “horse"와 word2 = “ros"의 경우를 분석해 보겠습니다:

  1. 초기화:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

       | ''| r | o | s
----+---+---+---+---
 '' | 0 | 1 | 2 | 3
----+---+---+---+---
 h  | 1 | ? | ? | ?
----+---+---+---+---
 o  | 2 | ? | ? | ?
----+---+---+---+---
 r  | 3 | ? | ? | ?
----+---+---+---+---
 s  | 4 | ? | ? | ?
----+---+---+---+---
 e  | 5 | ? | ? | ?

  2. DP 계산 후:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

       | ''| r | o | s
----+---+---+---+---
 '' | 0 | 1 | 2 | 3
----+---+---+---+---
 h  | 1 | 1 | 2 | 3
----+---+---+---+---
 o  | 2 | 2 | 1 | 2
----+---+---+---+---
 r  | 3 | 2 | 2 | 2
----+---+---+---+---
 s  | 4 | 3 | 3 | 2
----+---+---+---+---
 e  | 5 | 4 | 4 | 3

  3. 최종 결과: dp[5][3] = 3, 즉 “horse"를 “ros"로 변환하는 데 필요한 최소 연산 횟수는 3입니다.

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 초기화 (한 문자열을 비우는 경우)
    for i in range(m + 1):
        dp[i][0] = i  # 삭제 연산
    for j in range(n + 1):
        dp[0][j] = j  # 삽입 연산

    # DP 점화식 적용
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:  # 문자가 같다면 변경 필요 없음
                dp[i][j] = dp[i - 1][j - 1]
            else:  # 삽입, 삭제, 변경 중 최소 비용 선택
                dp[i][j] = min(dp[i - 1][j] + 1,  # 삭제
                               dp[i][j - 1] + 1,  # 삽입
                               dp[i - 1][j - 1] + 1)  # 변경

    return dp[m][n]

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var minDistance = function(word1, word2) {
    let m = word1.length, n = word2.length;
    let dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    // 초기화 (한 문자열을 비우는 경우)
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    // DP 점화식 적용
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(dp[i - 1][j] + 1,  // 삭제
                                    dp[i][j - 1] + 1,  // 삽입
                                    dp[i - 1][j - 1] + 1);  // 변경
            }
        }
    }

    return dp[m][n];
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform