편집 거리 - DP

 본 문제는 반복적으로 문자 삽입, 삭제, 교체 중 최적의 선택을 시행한다는 점에서 DP로 접근한다는 아이디어는 타당하다.

 소개할 방법에서는 기본적으로 문자열 A를 순회하며 문자열 B와 비교해 현재 인덱스에 해당하는 문자에 와야할 문자를 삽입할지, 삭제할지, 교체할지 결정한다. 아래 표는 A에 sunday, B에 saturday가 입력된 경우 편집 거리 DP 테이블 이다. 여기서 편집 거리란 특정 행상태의 A가 특정 열상태의 B까지 도달하기 위한 최소 비용이다.

  맨 처음 테이블을 초기화 할 때는, 문자열 A가 아무것도 입력되지 않았을 때 B의 saturday까지 입력되려면 총 8의 편집 거리가 소요되므로 dp[0][8] = 8 이 되고, 마찬가지로 문자열 B가 비어있을 때 A의 sunday가 되려면 총 6의 편집 거리가 들기 때문에 dp[6][0] = 6 이 되는 것이다. 그 뒤로 테이블을 채워 나가는것은 상기한 것과 같이 삽입, 삭제, 교체 중 가장 최적의 선택을 하며 진행하는데, 예를 들면 dp[1][3]의 경우 A를 기준으로 보면 "s"가 B의 "sat"까지 가야하는 상태이니, "sa" 상태까지 편집한 뒤 그저 "t"를 붙여줄지, "s"를 지우고 아예 "sat"를 입력해버릴지, 아니면 애초에 현재 문자 "s"를 쓰지 않고 "sa"까지 간 뒤 이 "s"를 "t"로 바꿔줄지 결정한다는 것이다. 다른 예를 들어보자. dp[6][8] 까지 도달 하는 경우는 "saturda"에 y를 삽입하는 경우, A[6] 즉 "y"를 사용하지 않고 "saturda"까지 편집한 다음 "y"를 "y"로 교체하는 경우 (이 경우 같은 문자 이므로 사실 상 교체는 아님), 마지막으로 "y"를 쓰지 않고 "saturday"까지 완성하고 남아버린 "y"를 삭제하는 경우가 존재할 것이고, 이들 중 가장 값이 작은것을 선택했을 때 최적의 편집 거리가 도출될 것이다. 결과적으로 다음과 같은 점화식이 세워진다.

코드

def edit_dist(str1,str2):
  n = len(str1)
  m = len(str2)
  dp = [[0]*(m+1) for _ in range(n+1)]
  
  # DP 테이블 초기 설정
  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 str1[i-1] == str2[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])
      
      return dp[n][m]

str1 = input()
str2 = input()

print(edit_dist(str1,str2))