Edit Distance

DP 알고리즘의 대표유형 5가지 중 마지막 편집 거리, Edit distance 문제에 대해 다뤄보자.

어떠한 문자열이 주어졌을 때, 다른 문자열로 바꾸기 위해 몇 번의 작업이 필요한지 알아내는 문제다. LCS문제와 조금 유사하지만 조금 더 까다로웠던 것 같다.

DP 리스트들을 채워가는 과정을 통해 어떻게 최소 작업 횟수를 얻을 수 있는지 알아보자.

Crepe

먼저 빈 문자열과 ‘ABCDE’ 그리고 빈 문자열과 ‘XABZDEY’를 비교해보자. 당연하게도 빈 문자열을 길이 n의 문자열로 바꾸기 위해서는 n번의 작업이 필요하다. 따라서, A,B,C,D,E의 밑에는 1,2,3,4,5 그리고 X,A,B,Z,D,E,Y의 옆에는 1,2,3,4,5,6,7이 들어가게 된다. (빈 문자열 끼리는 0번의 작업이 필요함으로 (0,0)에는 0을 넣어준다.)

이제 오른쪽 표를 보며 ‘ABCDE’에 대해 ‘X’, ‘XA’, ‘XAB’는 몇 번의 작업이 필요한지 알아보자.

  • X 와 A는 1번만 수정하면 된다. 총 1번 작업한다.
  • X 와 AB는 1번 수정, 1번 추가 작업이 필요하다. 총 2번 작업한다.
  • X 와 ABC는 1번 수정, 2번 추가 작업이 필요하다. 총 3번 작업한다.

  • ABCD와 ABCDE에 대해서도 동일하게 작업을 추가해준다.

  • XA 와 A는 1번만 추가하면 된다. 총 1번 작업한다.
  • XA 와 AB는 2번 수정 작업이 필요하다. 총 2번 작업한다.
  • XA 와 ABC는 2번 수정, 1번 추가 작업이 필요하다. 총 3번 작업한다.

  • ABCD와 ABCDE에 대해서도 동일하게 작업을 추가해준다.

  • XAB 와 A는 2번만 추가하면 된다. 총 2번 작업한다.
  • XAB 와 AB는 1번 추가 작업이 필요하다. 총 1번 작업한다.
  • XAB 와 ABC는 1번 삭제, 1번 추가 작업이 필요하다. 총 2번 작업한다.
  • ABCD와 ABCDE에 대해서도 동일하게 작업을 추가해준다.

이와 같은 방식으로 dp표를 모두 채운다.

이제 DP의 점화식, 규칙에 대해 생각해보자. ABCD와 XABZD의 작업횟수와 ABC와 XABZ의 작업횟수를 생각해보자. 만약에 두 문자열에 추가되는 문자가 같다면 추가되기 전과 후의 작업횟수는 동일할 것이다. 따라서, 동일한 두 문자가 각각 추가되는 경우 dp[i][j]=dp[i-1][j-1]이다.

추가되는 문자의 종류가 다른 경우는 어떻게 될까? 이전 문자열에 수정, 삭제, 추가 중 한 가지 작업을 반드시 추가해야 함으로, dp[i][j]는 dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1 중 가장 작은 값이 될 것이다. 따라서, dp[i][j]=min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)

아래의 표에서 확인해보자. ((0,0)에서 (5,7)로 가는 경로는 한가지 이상일 수 있다.)

Crepe

또한, 복사 수정 추가 삭제가 되는 경우는 아래와 같이 확인할 수 있다.

  • dp[i][j]=dp[i-1][j-1]일 때 ‘복사’
  • dp[i][j]=dp[i-1][j-1]+1일 때 ‘수정’
  • dp[i][j]=dp[i-1][j]+1일 때 ‘추가’
  • dp[i][j]=dp[i][j-1]+1일 때 ‘삭제’

최소 작업 횟수를 구하는 코드는 아래와 같다.

CODE

import sys
n = int(input())
numbs = list(int(sys.stdin.readline()) for _ in range(n))

dp = list(0 for _ in range(n+1))

for i in range(n):
    for j in range(i):
        if numbs[i] > numbs[j] and dp[i] <= dp[j]:
            dp[i] = dp[j]+1
    if dp[i] == 0:
        dp[i] = 1

print(n-max(dp))


편집 거리

7620번 편집 거리 문제는 이 외에도 ‘복사 수정 추가 삭제’ 작업이 어떻게 진행되는지 차례로 출력하는 문제다. 현재 까지는 아래와 같이 풀었는데, 아직 정답인 코드를 제출하지 못했다. 최대한 최적화를 진행해 봤는데 메모리 초과의 늪에서 벗어날 수 없었다.. 확인해보니 python3로 정답을 제출한 사람이 0명 이었다. 추후 다시 시도해 보고, 정답을 발견하면 다시 코드를 수정해서 올려야겠다.


CODE

a=input()
b=input()
na,nb=len(a),len(b)
#dp Setting
dp=list(list(0 for _ in range(na+2))for _ in range(nb+2))
for i in range(na+1):
    dp[0][i]=i
    dp[-1][i]=2147000000
for i in range(nb+1):
    dp[i][0]=i
    dp[i][-1]=2147000000
dp[-1][-1]=2147000000
#put values in dp
for i in range(1,nb+1):
    for j in range(1,na+1):
        if b[i-1]==a[j-1]:
            dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
        else:
            dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1

i,j=0,0
while True:
    minimum=min(dp[i+1][j],dp[i][j+1],dp[i+1][j+1])
    if dp[i+1][j+1]==minimum and dp[i][j]==dp[i+1][j+1]:
        print('c',b[i])
        i,j=i+1,j+1
    elif minimum==dp[i+1][j+1] and i!=0:
        print('m',b[i])
        i,j=i+1,j+1
    elif minimum==dp[i+1][j]:
        print('a',b[i])
        i,j=i+1,j
    elif minimum==dp[i][j+1]:
        i,j=i,j+1
    if i==nb and j==na: break


DP 대표 유형

[다시 풀어보기]