[백준15483번] 최소 편집 / Python3

문제

두 문자열 A와 B가 주어졌을 때, A에 연산을 최소 횟수로 수행해 B로 만드는 문제를 "최소 편집" 문제라고 한다.

A에 적용할 수 있는 연산은 총 3가지가 있으며 아래와 같다.

1. 삽입: A의 한 위치에 문자 하나를 삽입한다.
2. 삭제: A의 문자 하나를 삭제한다.
3. 교체: A의 문자 하나를 다른 문자로 교체한다.

두 문자열이 주어졌을 때, 최소 편집 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 최소 편집 횟수를 출력한다.

예제 입력 1

abc
ab

예제 출력 1

1

예제 입력 2

ca
abc

예제 출력 2

3

나의 풀이

해당 문제는 두 문자열의 편집 거리(edit distance), 혹은 레벤슈타인 거리(levenshtein distance)라고 불리는 알고리즘을 사용하여 푸는 문제였다. 이 알고리즘은 DP를 사용하여 답을 도출해낸다.

문제에서도 주어졌듯 편집에서 적용할 수 있는 연산은 세 가지가 있다.

1. 삽입 : abc -> abcd
2. 삭제 : abc -> ab
3. 수정 : abc -> adc

이러한 세 가지의 경우의 수를 이용하여 DP를 적용하여 문제를 풀어나갈 수 있다. 우선, dp 2차원 배열이 필요하다. 행은 A문자열, 열은 B의 문자열로 이루어져 다음과 같이 그려질 수 있다.

A : LOVE, B : MOVIE

     null M  O  V  I  E
null  0   1  2  3  4  5 
 L    1   ?
 O    2
 V    3
 E    4

dp[i][j]의 의미는 A의 i번째까지의 부분문자열에서 B의 j번째 부분문자열을 만들어내는데 필요한 최소 편집의 횟수이다. 따라서 초기화를 위와 같이 해줄 필요가있다. 첫번째 행을 예로들면, 빈 문자열 null에서 null을 만들려면 0번의 편집, M을 만들기위해서는 M을 한 번 추가해야하므로 1번의 편집 횟수, MO를 만들기 위해서는 M, O를 추가하는 2번의 연산이 필요하므로 2번...과 같이 초기화를 하게된다. 반대로 첫번째 열은 L에서 null을 만들기 위해서는 L을 한번 삭제하는 연산이 필요하므로 1번의 횟수가 필요하게 된다.

이제 초기화까지 하였다면, DP의 꽃인 점화식을 구해야한다. 점화식은 다음과 같다.

dp[i][j] = min(dp[i-1][j] + 1, 
                             dp[i][j-1] + 1, 
                             dp[i-1][j-1] + cost(i,j))

위의 점화식을 표에서 쉽게 생각해보면 바로 왼쪽, 왼쪽 위, 위쪽의 값들 중 최솟값에 1을 더해주는 것이다. 그러나 마지막 왼쪽 위의 값에는 1이 아닌 cost(i,j)가 있다. 이는 A문자열 i번째의 문자와 B문자열 j번째 문자가 다를 경우에는 1, 같을 경우에는 0을 나타내는 것이다. 왜냐하면 해당 문자들이 같다면 편집을 거칠 필요가 없다고 생각하면 쉽게 이해할 수 있을 것이다. 즉, 왼쪽 위의 요소를 그대로 복사를 하는 것이다. 위의 점화식을 통해 dp과정 반복을 끝내면 dp배열은 다음과 같다.

     null M   O    V   I   E
null  0   1   2    3   4   5 
 L    1   1   2    3   4   5 
 O    2   2  (1)   2   3   4     
 V    3   3   2   (1)  2   3   
 E    4   4   3    2   2  (2)

()는 위에서 말한 cost(i,j)가 0인 경우에 해당할때이다.

코드

# 15483번 최소 편짐

s1 = input()
s2 = input()
s1_size = len(s1)
s2_size = len(s2)

d = [[0] * (s2_size+1) for _ in range(s1_size+1)]   # dp배열

# 초기화
for i in range(s1_size+1):
    d[i][0] = i
for i in range(s2_size+1):
    d[0][i] = i

# DP
for i in range(1, s1_size+1):
    for j in range(1, s2_size+1):
        if s1[i-1] == s2[j-1]:
            d[i][j] = d[i-1][j-1]
        else:
            d[i][j] = min(d[i-1][j-1], min(d[i-1][j], d[i][j-1])) + 1

print(d[s1_size][s2_size])