[Algorithm] Edit Distance (편집 거리)

0. 문제

link: https://www.codetree.ai/missions/6/concepts/35/problems/minimum-edit/description

코드트리

(추천글을 하도 써서 광고를 의심받을 것 같긴 한데..진짜 좋다..광고비는 따로 안 받는다)

(당연함 누가 이런 하루에 5명오는 블로그에 광고를 걸어)

 

편집 거리란, 문자열 A, B가 주어졌을 때, 문자열 A를 문자열 B로 바꾸기 위해 필요한 최소 변경 횟수를 의미한다.

변경은 하나의 문자를 변경하거나, 삭제하거나, 원하는 위치에 삽입하는 경우가 있다. 

1) 변경, 삭제만 가능할 때와 2) 삽입까지 가능할 때의 풀이가 다르다. 둘 다 아래에서 자세히 살펴보겠다. 

 

1. 풀이 

 

1) 삽입, 삭제만 가능할 때 

 

이 때는 LCS와 깊은 연관이 있다. LCS에 대한 설명은 아래 링크에 서술되어 있다.

https://codinglilly.tistory.com/21

LCS를 찾았다는 것은, LCS를 제외한 부분을 같게 만들어주면 두 문자열을 같게 만들 수 있다는 의미이다. 

그림으로 나타내면 다음과 같다.

SABSBA, ABABSA의 LCS

 

A를 B로 바꾸는 것이 목적이므로, 다른 부분인 S와 B를 삭제하고, B와 같은 위치에 A와 B를 삽입하면 된다.

삭제 2번, 삽입 2번의 연산이 일어나는데, 이는 (6-4) + (6-4) 로 볼 수 있다.

즉, LCS와 다른 부분을 A에서 삭제하는 (6-4), B와 같은 부분을 삽입하는 (6-4) 번의 연산이 일어나는 것이다. 

따라서 이 때는 A의 길이를 n, B의 길이를 m, LCS의 길이를 x라고 하면 (n-x) + (m-x) 가 편집 거리가 된다.

 

2) 삽입, 변경, 삭제가 가능할 때

 

이 경우에는 LCS로 풀 수 없다. 변경이 가능하므로 위치를 고려해야 하고, LCS는 위치의 일치를 고려하지 않았기 때문이다.

이때는 동적 계획법으로 접근해야 한다. 

dp[i][j]를 A의 i번째, B의 j번째까지의 편집 거리라고 하자. 

이 때, A의 i번째, B의 j번째를 선택하냐, 선택하지 않느냐의 문제로 볼 수 있다. 단 선택을 갖다 쓰는 것이 아닌 해당 위치에서 연산을 수행할 것인가의 개념으로 보면 좋겠다. A의 i번째를 a, B의 j번째를 b라고 하겠다.

 

a와 b가 같다면 그냥 붙이면 된다. 따라서 편집 거리는 A의 i-1번째, B의 j-1번째까지의 편집 거리에 1만 더해주면 된다.

문제는 a와 b가 다를 때 발생한다. 

 

① a를 선택할 경우: A를 B로 바꾸는 것이 목적이므로, a를 쓰기로 선택했는데 다를 때는 삭제해야 한다. 따라서 dp[i-1][j]에 삭제 연산을 한 번 추가한 것이 된다.

② b를 선택할 경우: A를 B로 바꾸는 것이 목적이므로, b를 쓰기로 선택했는데 다를 때는 a의 이전 자리에 b를 추가해야 한다. 따라서 dp[i][j-1]에 삽입 연산을 한 번 추가한 것이 된다. 

③ a와 b를 둘 다 선택한 경우: 둘 다 쓴다고 선택한 것은 둘을 같다고 간주하는 것이다. 따라서 a를 b로 바꿔주는 경우이므로 dp[i-1][j-1]에 변경 연산을 한 번 추가한 것이 된다. 

 

이를 점화식으로 나타내면 다음과 같다.

dp[i][j] = dp[i-1][j-1] + 1 (if a==b)

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 (if a != b)

 

2. 구현

 

obj = list(input())
tgt = list(input())
n1 = len(obj)
n2 = len(tgt)

# 첫 번째 시작을 공집합으로 간주하고 dp를 만든다.
dp = [[0 for _ in range(n2+1)] for _ in range(n1+1)]
lcs = []

# 공집합과 문자열을 비교하면 문자열의 길이가 dp의 값이 된다.
for i in range(1, n1+1):
    dp[i][0] = i
for j in range(1, n2+1):
    dp[0][j] = j

# dp[i][j]: i번째와 j번째까지를 비교했을때의 edit distance
for i in range(1, n1+1):
    for j in range(1, n2+1):
        # 두 문자열의 끝이 같을 경우 연산을 할 필요가 없다. 따라서 이전의 값을 끌고 온다.
        if obj[i-1] == tgt[j-1]:
            dp[i][j] = dp[i-1][j-1]
        # 끝이 다를 경우
        # dp[i-1][j]: obj에서 하나를 삭제한 경우
        # dp[i][j-1]: tgt에서 문자를 하나 추가한 경우
        # dp[i-1][j-1]: 두 문자열이 같다고 보는 것, 즉 교체의 경우
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
for i in range(n1):
    print(dp[i])

print(dp[n1][n2])

문자열의 첫 번째가 공집합이라고 간주하면 초기화가 쉬워진다. 공집합에는 무조건 해당 문자를 추가하는 것이 가장 짧은 편집 거리가 되기 때문이다. 이후 위의 점화식을 수행해준다.