Q36. 편집거리 (리벤슈타인 거리, edit distance)

편집거리에 대한 설명이 잘 나와있는 블로그를 봤다

편집 거리 알고리즘(Levenshtein Distance, Edit Distance) :: 화투의 개발 블로그 (tistory.com)

편집 거리 알고리즘(Levenshtein Distance, Edit Distance)

 

편집거리 알고리즘은 정말 유명한 알고리즘이다.

두 배열을 동일하게 만드는 연산의 최소 개수를 구하는 알고리즘.

 

배열 arr1과 arr2가 있다고 치고

f(i,j) = arr1[:i]와 arr2[:j]의 편집 거리라고 치자

f(i,0) = i

f(0,j) = j 가 base케이스다. 직접 생각해보면 알거다. 

f(i,j)는 크게 두 가지 케이스로 나눠야 된다.

(1) arr1[i] == arr2[j]인 경우

이 경우에는 arr1[:i-1]과 arr2[:j-1]의 편집거리랑 똑같다.

끝문자가 같으니 편집할거리가 없기 때문이다

(2) arr1[i] != arr2[j]인 경우

arr1[i]와 arr2[j]가 같아지려면 어떻게 해야될까?

이 경우는 세 가지 가능성이 있다.

A. arr1[i]를 arr2[j]로 수정해서 맞추는 경우

f(i-1,j-1) + 1

B. arr1[:i-1]에 arr2[j]를 추가해서 맞추는 경우

f(i-1,j) + 1

C. arr2[j]를 삭제하는 경우

f(i,j-1) + 1

최소 편집 거리를 구해야 되니까 세 값중 minimum값을 찾으면 된다.

시간복잡도는 arr1의길이가 N이고 arr2의 길이가 M일때 O(NM)

 

코드로 구현하면 다음과 같다.

 

def ed(arr1,arr2):
    dp = [[0] * (len(arr2)+1) for _ in range(len(arr1)+1)]
    for i in range(len(arr1)+1):
        dp[i][0] = i
    for j in range(len(arr2)+1):
        dp[0][j] = j
    
    for i in range(1,len(arr1)+1):
        for j in range(1,len(arr2)+1):
            if arr1[i-1] == arr2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = min(dp[i-1][j]+1, dp[i-1][j-1]+1, dp[i][j-1]+1)

    return dp[len(arr1)][len(arr2)]

str1 = input()
str2 = input()

print(ed(str1,str2))