[DP] 편집거리

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

- 2개의 string이 주어질 때 1번째 string을 2번째 string으로 바꾸기 위해서 '삽입, 삭제, 교체'등의 연산을 수행할 수 있다. 이때, 최소한의 연산을 수행했을 때의 값은?

2. 접근 방식

- 2차원 배열의 DP를 활용해서 문제를 풀면된다.
- 두 문자가 같은 경우 : dp[i][j] = dp[i-1][j-1]
- 두 문자가 다른 경우: dp[i][j] = 1+ min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] (삽입, 삭제, 교체 순)

3. 코드

## 최소편집거리 계산을 위한 DP
def edit_dist(str1, str2):
    n = len(str1) # soruce
    m = len(str2) # target
    
    dp = [[0]*(m+1) for _ in range(n+1)] # source데이터를 행으로, target를 열로
    
    for i in range(1, n+1):
        dp[i][0] = i # source
    for j in range(1, m+1):
        dp[0][j] = j  # target
    
    # 최소편집 거리 계산
    for i in range(1, n+1):
        for j in range(1, m+1):
            if str1[i-1] == str2[j-1]: # str과 dp의 인덱스는 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))

4. 코멘트

- 삽입, 삭제, 교체 연산을 이해하는데 시간이 좀 걸렸었던 것 같다. i와 j를 기준으로 했을 때 삽입의 경우 i(행)는 가만히 있고, j(열)만 움직인다는 생각을 하면 되고, 삭제의 경우 j(열)은 가만히 있고, i(행)만 움직인다는 느낌으로 이해했다.

- 추가적으로 백준 실습 코드가 있는 줄 알고 편집거리 문제를 풀었는데, 알고보니까 다른 문제여서 내친김에 풀려고 했다. 하지만 메모리 초과가 계속해서 나와서 어쩔 수 없이 다음 기회로 넘겼다. (함수를 없애고, 출력 리스트를 dp와 함께 생성해봐야겠다.)