[DP] 이코테 “편집 거리” Python 풀이

문제

• 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다.
• 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.
  1. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다.
  2. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다.
  3. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.
• 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다.
• 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요.
• 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다.

입력 조건

• 두 문자열 A와 B가 한줄에 하나씩 주어집니다.
• 각 문자열은 영문 알파벳으로만 구성되어 있으며 , 각 문자열의 길이는 1보다 크거나 같고, 5,000보다 작거나 같습니다.

출력 조건

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

입력 예시

cat
cut

sunday
saturday

출력 예시

1

3

풀이

• 이 문제는 최소 편집 거리를 담을 2차원 테이블을 초기화한 뒤에, 최소 편집 거리를 계산해 테이블에 저장하는 과정으로 문제를 해결할 수 있다.

• 다이나믹 프로그래밍의 점화식은 다음과 같다.

    # 두 문자가 같은 경우
    dp[i][j] = dp[i - 1][j - 1]
  
    # 두 문자가 다른 경우
    dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

• 이를 말로 풀어서 쓰면 다음과 같다.

  • 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
  • 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중에서 가장 작은 수에 1을 더해 대입

• 예를 들어, “sunday”를 “saturday”로 변경한다고 해보자.

• 이때 초기 2차원 테이블은 다음과 같이 구성된다.

  

• 왼쪽(열)에 있는 “sunday”라는 문자열을 위쪽(행)에 있는 “saturday”로 변경하는 비용을 계산할 수 있도록 이와 같이 테이블을 구성한 것이다.

• 여기에서 ∅는 빈 문자열을 의미한다.

• 빈 문자열을 “saturday”로 만들기 위해서는 8개의 문자를 삽입해야 하기 때문에, 테이블의 dp[0][8]의 값은 8이다.

• 이제 점화식에 따라서 전체 테이블을 차례대로 갱신해주면 다음과 같다.

  

• 2차원 테이블은 왼쪽(열)에 있는 문자열을 위쪽(행)에 있는 문자열로 바꾸는 비용을 직관적으로 보여준다.

• 예를 들어 dp[2][3]의 값은 2인데, 이는 “su”라는 문자열을 “sat”이라는 문자열로 바꾸기 위한 최소 편집 거리가 2라는 의미가 된다.

• 결과적으로 테이블의 가장 오른쪽 아래에 있는 값이 구하고자 하는 최소 편집 거리가 된다.

• 즉, 아래 예시에서 최소 편집 거리는 3이다.

예제 코드

# https://www.acmicpc.net/problem/15483

import sys

# 두 문자열 입력
a = sys.stdin.readline()
b = sys.stdin.readline()

# 최소 편집 거리 계산을 위한 DP 테이블 생성
dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]

# 최소 편집 거리 계산
for i in range(len(a)+1):
    for j in range(len(b)+1):
        # 첫 번째 행일 경우
        if (i == 0):
            dp[i][j] = j
        # 첫 번째 열일 경우
        elif (j == 0):
            dp[i][j] = i
        else:
            # 현재 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
            if (a[i-1] == b[j-1]):
                dp[i][j] = dp[i-1][j-1]
            # 현재 문자가 다르다면, 
            # 세 가지 경우[삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위)] 중에서 최솟값을 찾고 +1 
            else:
                dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])

print(dp[len(a)][len(b)])

참고

• 이것이 취업을 위한 코딩 테스트다. with python
• https://velog.io/@embeddedjune/알고리즘-이것이-코딩-테스트다-DP-Q36-편집-거리