편집 거리 골드만삭스 DP

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

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

일단 드는 생각은 문자열을 변경을 하고 추가를 하든 추가를 하고 변경을 하든 다 동일하다는 생각이었습니다.

거기에다가 문자열이다보니 1차원 배열에서 어떻게 조작을 하면 될까 고민했는데… 결국 이 문제는 최소 편집 거리를 2차원 테이블에 초기화해서 편집거리를 계산해 테이블에 저장하는 방식으로 해결 했습니다. 테이블을 갱시하는 과정이었기에 다이나믹프로그램의 점화식이 사용됩니다. (.. 생각도 못했네요)

일단 두 문자와 같은 경우 두가지로 구분 할 수 있습니다.

행과 열에 해당하는 문자가 서로 같다면 왼쪽위에 있는 수를 그대로 대입

행과 열에 해당하는 숫자가 서로 다르다면 왼쪽(삽입), 위쪽(삭제), 왼쪽 위(교체)에 해당하는 수 중에서 가장 작은 수에 1을 더해 대입

이를 DP의 점화식은 다음과 같이 표현합니다.

1) 두 문자가 같은 경우 : dp[i][j] = dp[i-1][j-1]

2) 두 문자가 다른 경우 : dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])

#최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(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] = 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))

생각 외로 코드가 굉장히 단순한 편입니다. 테이블을 직접 적어가면서 살펴보겠습니다.

	None	s	a	t	u	r	d	a	y
None	0	1	2	3	4	5	6	7	8
s	1
u	2
n	3
d	4
a	5
y	6

맨 처음 테이블을 이렇게 초기화가 됩니다. 그러면 각 숫자는 해당 위치의 낱말을 만드는데 필요한 비용이 들어가게 됩니다.

예를 들어서 첫번째 줄의 d줄로 가봅시다. 비용이 4가 됩니다. sund에서 None이 되기 위해서는 제거를 4번 해야하니 총 비용이 4가 됩니다. 각 숫자는 일단 여기 위치에서 None까지드는 비용이 되겠는데 이제 다음으로 가봅시다.

s와 s가 만나는 지점의 경우 두 단어가 동일합니다. 그러면 변경사항이 없으니 (i-1,j-1)지점인 0,0의 값 0을 가져옵시다. sa가 s가 되기위해서는 비용이 1필요 합니다. 첫번째 줄은 s부터 y까지 쭉 비용이 1씩 증가하겠네요

	None	s	a	t	u	r	d	a	y
None	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1
n	3
d	4
a	5
y	6

이제 u 열로 가봅시다. 일단 su를 s로 바꾸는 것에서 비용이 1들어갑니다. 그리고 그 다음칸으로 왔을때 su와 sa를 비교하는게 되는데 인접한 곳에서(삽입,삭제,교체) 중에서 가장 싼 비용은 0이고 여기서 1을 더한 값 1을 반환을 하게 됩니다.

	None	s	a	t	u	r	d	a	y
None	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3
d	4
a	5
y	6

su와 satu를 비교하는 지점 역시 마찬가지 입니다. 주변에서 가장 싼 비용은 1에서 1을 더해준 2가 됩니다.

	None	s	a	t	u	r	d	a	y
None	0	1	2	3	4	5	6	7	8
s	1	0	1	2	3	4	5	6	7
u	2	1	1	2	2	3	4	5	6
n	3	2	2	2	3	3	4	5	6
d	4	3	3	3	3	4	3	4	5
a	5	4	3	4	4	4	4	3	4
y	6	5	4	4	5	5	5	4	3

마지막 끝의 y의 경우 두 문자가 같으니 그 앞에 있는 3을 그대로 가져와서 마무리 하게 됩니다.

이렇게 각 두 문자열에 대해서 어떤식으로 변경을 할 수 있을지 모든 비용을 계산하게 되고 이를 메모하는 형식으로 나가니 다이나믹프로그래밍 문제가 되었습니다.