36_편집 거리

이 문제는 최소 편집 거리를 담을 2차원 테이블을 초기화한 뒤, 최소 편집거리를 계산해 테이블에 저장하는 과정으로 문제를 해결할 수 있다.

 

점화식은 다음과 같다.

두 문자가 같은 경우: dp[i][j] = dp[i-1][j-1]
행과 열에 해당하는 문자가 서로 같다면 왼쪽 위에 해당하는 수를 그대로 대입

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

 

 

 

만약 문자열 A의 i번째 문자와 문자열 B의 j번째 문자가 같은 경우

- 두 문자가 같다면 연산이 필요하지 않으므로 dp[i-1][j-1]의 값을 그대로 가져온다.

 

만약 문자열 A의 i번째 문자와 문자열 B의 j번째 문자가 다른 경우

A

- SU와 SAT 사이의 편집거리는 S와 SA 사이의 편집거리에서 수정 연산을 한번 더하면 된다.

- S와 SA 사이의 편접거리는 A를 추가하는 연산 1번

- 거기다가 U를 T로 변환하는 연산 1번을 추가하는 것.

그래서 2

 

B

- SU와 SAT 사이의 편집거리는 S와 SAT 사이의 편집거리에서 삭제 연산을 한 번 더 하면 된다.

- S와 SAT 사이의 편집거리는 A 추가, T 추가의 2번

- 거기다가 U를 삭제하는 연산 1번을 추가

그래서 3

 

C

- SU와 SAT 사이의 편집거리는 SU와 SA 사이의 편집거리에서 삽입 연산을 한번 더 하면 된다.

- SU와 SA 사이의 편집거리는 U를 A로 바꾸는 교체 연산 1번

- 거기다가 T를 추가하는 연산 1번을 추가

- 그래서 2

 

 

A, B, C 중 제일 적은 편집 거리 + 1을 dp[i][j]에 저장한다.

 

 

---

풀이 코드

 

# 편집 거리
# 최소 편집 거리 계산을 위한 DP
def edit_distance(str1, str2):
    n = len(str1)
    m = len(str2)

    # 2차원 dp 테이블 초기화
    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]

            # 문자가 다르다면, 3가지 경우 중 최솟값 찾기
            else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
                dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

    return dp[n][m]


str1 = input()
str2 = input()

print(edit_distance(str1, str2))

 

 

---

그림 출처

알고리즘 :: 이것이 코딩 테스트다 :: DP :: Q36 :: 편집 거리