[이코테/Python] 편집 거리 || 다이나믹 프로그래밍

이코테 편집 거리 파이썬

❍ 문제

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

❍ 입력

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

❍ 출력

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

❏ 문제 풀이

str과 str2를 쪼개어 비교하며, 최소 편집 거리를 구한다.
 

먼저, 공백과 [s, st, sto] 간의 최소 편집 거리를 구해보자.
 
공백 → s는 삽입 단계가 필요하므로 1, 공백 → st는 또다시 삽입 단계가 필요하므로 2.
따라서 각각 1, 2, 3이 될 것이다. (모두 삽입 단계 필요)
 
반대로 [s, st, str, stro]와 공백간의 최소 편집 거리는 각각 1, 2, 3, 4가 될 것이다. (모두 삭제 단계 필요)
여기까지를 회색 박스로 표현하였다.
 

• 핑크 - 단계 변화 없음
• 파랑 - 왼쪽, 삽입
• 초록 - 위쪽, 삭제
• 보라 - 왼쪽위, 교체

1. s → st는 s → s에서 t를 추가하는 삽입 단계가 추가된다. 따라서, s → s(0) + 1 = 1 여기서 s → s는 s → st에서 왼쪽에 위치한다.
2. st → s는 s → s에서 t를 삭제하는 삭제 단계가 추가된다. 따라서, s → s(0) + 1 = 1 여기서 s → s는 st → s에서 위쪽에 위치한다.
3. str → sto는 st → st에서 r에서 o로 교체하는 교체 단계가 추가된다. 따라서, st → st(0) + 1 = 1 여기서 st → st는 str → sto에서 왼쪽 위에 위치한다.
4. st → st는 어떠한 단계도 추가되지 않는다. 따라서, s → s(0)과 같다. 여기서 s → s는 st → st의 왼쪽 위에 위치한다.

이 외에도 여러 값들을 직접 계산해보면, 결국 아래와 같은 결과가 나온다.
삽입, 삭제, 교체와 같은 단계를 거치지 않아도 되는 경우는 i와 j에 해당하는 문자가 동일한 경우이다.

1. 두 문자가 동일하다면, 왼쪽 위와 동일하다.
   $$dp[i][j] = dp[i - 1][j - 1]$$
2. 두 문자가 동일하지 않다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체) 중 가장 최소 편집 거리에 해당하는 것에 1을 추가하면 된다.
   $$dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j -1]) + 1$$

 

❍ CODE

'''
< 편집 거리 >
'''

str1 = input()
str2 = input()

n, m = len(str1), 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] = i

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]
        else:
            dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1

print(dp[n][m])

 

❍ CODE

이 풀이는 2차원 리스트를 사용하지 않고 1차원 리스트만을 사용하여 공간 복잡도를 줄일 수 있다.

str1 = input()
str2 = input()
n, m = len(str1), len(str2)
previous = [i for i in range(m + 1)]
current = [0] * (m + 1)

for i in range(1, n + 1):
    current[0] = i
    for j in range(1, m + 1):
        if str1[i - 1] == str2[j - 1]:
            current[j] = previous[j - 1]
        else:
            current[j] = min(current[j - 1], previous[j], previous[j - 1]) + 1
    previous, current = current, previous

print(previous[-1])