202. 편집 거리

• 두 개의 문자열 A, B가 주어졌을 때, A를 편집하여 B로 만들려고 한다.

• 수행할 수 있는 연산은 다음 3가지다.

  1. 삽입(Insert): 특정한 위치에 문자 하나를 삽입합니다.

  2. 삭제(Remove): 특정한 위치에 문자 하나를 삭제합니다.

  3. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.

• 한 번에 하나씩 선택하여 사용할 수 있다.

• 이때 최소 편집 횟수를 구하시오.

• 입력조건

  • 두 문자열 A와 B가 한 줄에 하나씩 주어집니다.

  • 각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고, 5000보다 작거나 같습니다.

• 출력조건

  • 최소 편집 거리를 출력합니다.

1. 다이나믹 프로그래밍

def edit_dist(str1, str2):
  n = len(str1)
  m = len(str2)

  dp = [[0] * (m + 1) for _ in range(n + 1)]
  for i in range(1, n + 1):
    dp[i][0] = i #첫행 초기화
  for j in range(1, m + 1):
    dp[0][j] = j #첫열 초기화

  for i in range(1, n + 1):
   for j in range(1, m + 1):
     #문자가 같다면 왼쪽 위에 해당하는 수를 그대로 대입
     if str1[i - 1] == str2[j - 1]:
       dp[i][j] = dp[i - 1][j - 1]
     #문자가 다르다면, 3가지 경우 중에서 최솟값 찾기
     else: #삽입(왼쪽), 삭제(위쪽), 교체 (왼쪽 위) 중에서 최소 비용
      dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

  return dp[n][m]

str1 = input()
str2 = input()

print(edit_dist(str1, str2))

2. C++

#include <bits/stdc++.h>

using namespace std;

// 두 문자열을 입력 받기
string str1;
string str2; 

// 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
int editDist(string str1, string str2) {
    int n = str1.size();
    int m = str2.size();

    // 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
    vector<vector<int> > dp(n + 1, vector<int>(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[i - 1] == str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
            // 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
            else { // 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                dp[i][j] = 1 + min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1]));
            }
        }
    }

    return dp[n][m];
}

int main(void) {
    cin >> str1 >> str2;

    // 최소 편집 거리 출력
    cout << editDist(str1, str2) << '\n';
}