[이코테] 다이나믹 프로그래밍 - 편집 거리

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

두 개의 문자열 A, B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다.

• 삽입 : 특정한 위치에 하나의 문자를 삽입한다.
• 삭제 : 특정한 위치에 있는 하나의 문자를 삭제한다.
• 교체 : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다.

이 때, 편집 거리란, 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성해라. 예를 들어, sunday를 saturday로 편집하는 최소 편집 거리는 3이다.

입력조건

• 두 문자열 A, B가 한 줄에 하나씩 주어진다.
• 각 문자열은 영문 알파벳으로만 구성되어 있으며, 각 문자열의 길이는 1보다 크거나 같고 5,000보다 작거나 같다.

출력조건

• 최소 편집 거리를 출력한다.

사고과정

• DP테이블을 어떻게 활용하는 것인지 감도 오지 않았다.. 30분이 후딱 지나고 풀이를 보았다. 풀이를 보길 잘했다는 생각이 들었다. 전혀 예상하지 못한 풀이였음..
• DP 테이블을 2차원 리스트로 정의해서 풀었는데, 이 때 행 값을 문자열 A, 열 값을 문자열 B라고 생각하고 DP 테이블을 정의했다.

DP 테이블

• 위에서 주황색 칸을 갱신시켜야 하는데, 한 칸씩 loop를 돌면서 아래의 점화식을 수행하면 된다. 이 때, DP테이블 기준으로 왼쪽으로 업데이트 하는 것은 삽입을, 위쪽 값으로 업데이트하는 것은 삭제를, 왼쪽 위 대각선으로 업데이트하는 것은 교체를 의미한다.
• 두 문자열이 같으면 대각선 위쪽의 값으로 가져오고, 두 문자열이 다르면 삽입,삭제,교체 중 DP테이블에서의 최솟값 + 1로 업데이트 해준다.(소스 코드를 보는게 더 이해가 수월 할 듯..)
• 이 패턴을 외워놓는 것도 좋을 듯 하다..

풀이(스스로 못 푼 풀이)

# str1 -> str2로 편집하는 최소 거리
def edit_dist(str1, str2):
    n = len(str1)
    m = len(str2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    
    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]
            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))