편집거리 알고리즘

1. 문제 

문자열 A, B가 주어졌을 때, 문자열 A를 편집해서 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 삽입, 삭제, 교체 세 가지 연산 중 하나를 선택하여 이용할 수 있다. 이때 편집거리란 문자열 A를 편집하여 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하라. 예를 들어 "sunday"와 "saturday"의 최소 편집거리는 3이다.

 

2. 풀이 

이런 방식으로 dp 테이블을 만들면, dp[n][m]이 최소 편집거리가 된다. 

def edit_dist(str1, str2):
    answer=0
    n = len(str1)
    m = len(str2)

    dp = [[0] * (m+1) for _ in range(n+1)]
    
    # 초반 dp설정
    for i in range(m+1):
        dp[0][i]=i
    for j in range(n+1):
        dp[j][0]=j
    
    #dp돌면서 편집거리 갱신
    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])

    answer = dp[n][m]
    return answer

print(edit_dist("sunday","saturday"))