편집 거리

출처::  Goldman Sachs 인터뷰

분류:: DP

 

1. 문제 이해 및 해결과정

- 2차원 DP테이블 이용 1. 두 문자가 같은 경우 dp[i][j]=dp[i-1][j-1] , 행과 열에 해당하는 문자가 서로 같으면, 왼쪽 위에 해당하는 수 삽입 2. 두 문자가 다른 경우 dp[i][j]= 1 + min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) , 행과 열에 해당하는 문자가 서로 다르면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체) 에 해당하는 수 중 가장 작은 수에 1을 더해서 대입

a/b	0	s	a	t	u	r	d	a	y
0	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

dp[2,2]= a(s)가 b(s)가 되기 위한 최소 편집거리

dp[3.0]= a(sun)가 b(0)이 되기 위한 최소 편집거리

 → : 삽입이 일어나는 방향

 ↓ : 삭제가 일어나는 방향

 ↘ : 교체가 일어나는 방향 

 

2. 풀이방법

 1. DP

#최소편집거리
#
import sys
sys.stdin = open("input.txt","r")
a=input()
b=input()
n=len(a)
m=len(b)
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 a[i-1]==b[j-1]:
            dp[i][j]=dp[i-1][j-1]
        else: #다르면, 삽입,삭제,교체 중에 최소비용을 골라 대입
            dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])

print(dp[n][m])

3. 오답원인

 

4. 알게된 점