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

https://prpn97.tistory.com/63

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

1편에 설명이 있으니 참고해도 좋을 것 같다. 

Longest Common Subsequence 

바로 최장 공통 부분수열에 대해 알아보려 한다. 

 

먼저 최장 공통 부분수열의 길이에 대해 배워보자. 

이번에는 LCS[i-1][j-1] 이전에 확인해야 하는 것이 있다. 

두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰값을 표시하고,
두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 1을 더한다.

 

1편에서 구한 최장 공통 문자열과 다른 부분은 비교하는 두 문자가 다를 때이다. 

무슨 뜻이냐면, 이전에는 연속된 두 문자를 찾기 위해서는 중복되어야 하기 때문에,

같지 않은 값은 모두 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	1	1	1	1
C	0	0	1	2	2	2	2
D
F
E

동일하게 G에는 겹치지 않으므로 0으로 채운다. 그리고 B와 C를 주목해보자.

노란 칸은 기존에 알아보았던 두 문자가 같을 때 LCS[i-1][j-1]값을 찾아 1을 더한 것이다. 

그런데, 현재의 문자를 비교하는 과정 이전의 최장 공통 부분수열은 계속해서 유지된다. 

노란 칸이 채워지기 전에,  '현재의 문자를 비교하는 과정' 이전의 과정이 

바로 LCS[i - 1][j] / LCS[i][j - 1]가 된다.

 

말로 풀어서 설명하면, AB, GB를 비교하면 최장 공통 부분 수열은 B가 된다. 

AB,GBC의 최장 공통 부분수열은 어떻게 되는 것인가? 역시 B가 된다. 

왜냐하면 LCS[i - 1][j] / LCS[i][j - 1]을 탐색하기 때문이다. 

즉, 값의 왼쪽과 위를 탐색해서 큰 값을 더하는 것이다.

 

내가 공부하지 않은체로 논리적으로 유추하려 했을 때는, 겹치면 1씩 늘리는 것 같은데..

왜 그 다음줄로 넘어가면 다시 0으로 시작하지?라는 궁금증이 있었는데, 

그게 아니라 주변 값을 확인하면서 값을 늘리는 것이였다.

 

그리고 부분수열이 연속될 필요가 없기 때문에 값을 그대로 유지하면서, 

문자열을 비교하다가 같은 값이 나오면 다시 한 번 이전에 더했던 값을 확인하고,

1을 더하는 것이다.

ABC,GBC의 최장 공통 부분수열 = AB,GB의 최장 공통부분수열 + 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	1	1	1	1
C	0	0	1	2	2	2	2
D	0	0	1	2	3	3	3
F	0	0	1	2	3	3	4
E	0	0	1	2	3	4	4

부분수열의 길이는 4가 된다.

 

 

이제 최장공통 부분수열의 값을 찾아보자. 

값은 여러 가지가 나올 수 있고, 과정을 같이 진행해보려 한다. 

 

먼저 부분수열의 값을 체크해야 하는데, 알고리즘이니 배열로 담듯 구상을 해보자.

result라는 칸을 새로 만들어보겠다. 

 

LCS 배열의 가장 마지막인 맨 구석의 4에서부터 거슬러 올라갈 것이다. 

해당 값에서 LCS[i-1][j], LCS[i][j-1]중 같은 값을 찾고, 있으면 이동한다.

같은 값이 없다면 result에 해당 문자를 넣고 LCS[i-1][j-1]으로 이동한다.

계속 반복하다가 0으로 이동하게 되면 종료한다. 

result에 들어간 값을 거꾸로 하면 LCS값을 확인할 수 있다. 

 

위 예시에는 둘 다 같은 값이므로, 하나를 선택해보자. 

		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	1	1	1	1
C	0	0	1	2	2	2	2
D	0	0	1	2	3	3	3
F	0	0	1	2	3	3	4
E	0	0	1	2	3	4	4

위를 선택했다. 그리고 다시 LCS[i-1][j], LCS[i][j-1]중 같은 값(노란색)을 찾는다.

4에서 왼쪽과 위를 봤는데 3밖에 없다.

그렇다면 같은 값이 없을 때는 result배열에 해당 값을 넣고, LCS[i-1][j-1]로 이동한다.

F

쉽게는 왼쪽 대각선(파란색)으로 이동하는 것이다.

이제 반복이다. 현재 파란 색인 상태에서 왼쪽과 위를 살피고 같은 값이 있으면

같은 값으로 이동한다. 왼쪽은 3이고, 위는 2이므로 3으로 이동해야겠다.

그 후에는 현재 3인 상태에서 왼쪽과 위 둘 다 2이므로,

값이 다르기 때문에 왼쪽 대각선 2로 이동한다. 이를 반복하다보면 다음과 같다. 

		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	1	1	1	1
C	0	0	1	2	2	2	2
D	0	0	1	2	3	3	3
F	0	0	1	2	3	3	4
E	0	0	1	2	3	4	4

이 표에서 결과를 알기 위해서는 대각선으로 이동하기 전에 위치한 값을 보면 된다.

예시에서는 FDCB다. 그리고 이 값의 역순인 BCDF 가 최장 부분수열, LCS값이다.

B

C

D

F