[다이나믹 프로그래밍] LCS, LCSS 란? 그리면서 이해하기 - 1

처음 문제를 접하며 도무지 이해가 안되서 정리해서 포스팅하며 되새기기 위해,

또한 나처럼 헤매고 있는 사람들이 있다면 답을 알기보다 과정들을 통해

이 알고리즘에 대해 이해하는데 도움이 될까 싶어 하나하나 써내리려 한다. 

구글링해보면, 많은 자료들이 있고, 함수로도 그림으로도 그려서 설명하는데,

바보인 나에겐 너무 어려워서, 초보의 시선에서 이해한대로 그려보려 한다. 

 

먼저 LCS란 무엇인가. 

Longest Common Substring혹은, Subsequence 이다. 

최장 공통 문자열 혹은 최장 공통 부분수열 이다. 

문자열 ABCDEF / GBCDFE가 있다고 하자.

최장공통 문자열은 BCD / 최장 공통 부분수열은 BCDF, BCDE가 될 수 있다. 

말 그대로 문자열을 비교해서 공통된 가장 긴 문자열 혹은 가장 긴 부분수열이다. 

 

처음 이 것을 이해하면서 답답했던 부분은, 여러 방법마다 칸에 어떻게 그리는지도,

무엇을 설명하려 하는지도, 문제가 의도하는 바가 무엇인지 이해가 되지 않았다.

내가 처음 접한 문제는 공통되는 문자 중 가장 긴 수열의 수를 구하는 것이였는데, 

4글자인 두 단어를 비교했을 때 똑같은 문자에 1을 넣으라는 것인지, 

답지를 보고도 어떻게 푸는지 감이 오지 않았다. 

 

바로 그려가며 표현해보겠다. 

		A	B	C	D	E	F
G
B
C
D
F
E

빈 칸에 해당되는 규칙에 맞게 숫자를 넣어볼텐데, 특이점은 비교하고자 하는 문자 외에도

행과 열이 하나씩 더 있다는 것이다. 함수로 생각해보면 LCS[i][j] 좌표를 찍는 것인데,

비교해서 같은 문자가 있으면 1, 없으면 0을 먼저 채워보자. 

G는 같은 문자가 없으므로 0으로 채우고, B는 같은 문자가 있으므로 해당 칸에 1을 채운다. 

그런데, 여기에서 단순히 1을 쓰는 것이 아니라, 

같은 문자가 존재하면 LCS[i][j]는 LCS[i-1][j-1]+1을 해주는 것이다. 

쉽게는, 왼쪽 위 대각선의 값에서 1을 더해주는 것이다. 

		A	B	C	D	E	F
	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0
C	0
D	0
F	0
E	0

쭉 이 규칙대로 해나가면 다음과 같다. 

		A	B	C	D	E	F
	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0
C	0	0	0	2	0	0	0
D	0	0	0	0	3	0	0
F	0	0	0	0	0	0	1
E	0	0	0	0	0	1	0

맨 마지막 1 을 채운 2개 역시 왼쪽 위 대각선 값이 0이기 때문에, 1을 더한 것이다. 

최장 공통 문자열은 이 규칙을 적용하여, BCD인 3이 된다. 

 

다음 포스트에서는 최장 공통 부분수열에 대해 써보려 한다.