LCS

LCS(Longest Common Subsequence)란 최장 공통 부분 문자열이다.

여기서 Subsequence는 부분 수열으로 문자열이 연속적일 필요는 없다는 것이다.

즉, 두 문자열을 비교할 때 공통 부분 수열 중 길이가 가장 긴 부분 수열을 의미한다.

예시로 "ACAYKP", "CAPCAK"를 보면 두 문자의 LCS는 ACAK다.

이 답을 어떻게 구할 수 있을까?

해결은 DP를 이용해 해결한다. 먼저 DP를 이용한 테이블을 먼저 봐보자.

DP		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

여기서 DP[3][5]는 ACAYKP의 3번째 문자 A, CAPCAK의 5번째 문자 A까지 비교한다. DP[3]을 예시로 들어보자.

DP[3][0]부터 DP[3][6]까지 가면서 비교를 하게된다. 만약 비교하게 되는 문자가 같지 않다면, 각 문자를 고려하기 전의 최댓값으로 반영한다.

DP[i][j] = max(DP[i-1][j], DP[i][j-1]

왜냐하면 문자가 같지 않다면, 현재 있는 부분 수열에서 가장 큰 값을 그대로 받기 때문이다.

여기서 각 문자라는 것은 두 문자열의 비교되는 문자이다. DP[3][5]라면 ACAYKP의 A와 CAPCAK의 A를 말한다.

DP[3][5]처럼 비교되는 문자가 같다면, DP[i][j] = DP[i-1][j-1] + 1 이다. 두 문자가 같기 때문에 두 문자를 비교하기 전 최댓값에 +1을 해주는 것이다.