[lecture]5주차.동적계획 알고리즘_편집 거리 문제

수업을 듣고 정리한 내용입니다.

편집거리 문제(edit distance)는 문서 편집기를 사용하는 중에 스트링 S를 수정해 다른 T로 변환하고자 할 때, 삽입(insert), 삭제(delete) 그리고 대체(sutstitude) 연산을 사용하는데 필요한 최소 편집 연산횟수를 계산하는 알고리즘이다. 문자를 편집할 때, 어떤 연산을 어느 문자에 수행하느냐에 따라 편집 연산 횟수가 달라지는데, 이를 부분문제를 정의하여 해결한다.

 

편집거리 문제에서 부분 문제는 접두부(prefix)를 확인하는 과정으로부터 시작된다. S의 길이를 m 그리고 T의 길이를 n이라 하고, 각각의 문자를 s_i, t_i라고 가정하였을 때, S = s1s2s3 ... sm, T = t1t2t3 ... tn이다. E[i,j]를 S의 처음 i개의 문자를 T의 처음 j개 문자로 바꾸는데 필요한 편집거리 라고 하였을 때, min{E[i, j-1] + 1, E[i-1, j] + 1, E[i-1, j-1] + a}으로 그것을 나타날 수 있다. 단, si과 tj가 다르다면 a값은 1이고 같다면 0이다.

 

EditDistance
입력 : 스트링 S, T. 단, S와 T의 길이는 각각 m과 n
출력 : S를 T로 변환하는 편집거리, E[m,n]
for i=0 to m	E[i,0] = i	//0번 열 초기화
for j=0 to n	E[0,j] = j	//0번 행 초기화
for i=1 to m
	for j=1 to n
    	E[i,j] = min{E[i,j-1] + 1, E[i-1,j] + 1, E[i-1,j-1] + a}
return E[m,n]

이 알고리즘의 시간 복잡도는 m과 n을 두 스트링의 각각의 길이라고 가정하였을 때, O(mn)이다. 총 부분 문제의 수가 배열 E의 원소 수인 m*n이며, 각 부분 문제인 원소를 계산하기 위해 주위의 3개의 부분문제의 해를 참조한 후 최솟값을 찾는 부분에 대한 시간복잡도는 O(1)이 소요되기 때문이다.