[ DP - 9251 ] LCS(C++)

 

---

접근법

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 여기서 부분 열은 상대적인 순서를 유지해야 하는데, 예를들어 ACAYKP의 부분 수열은 ACA, ACP, CYK, CAP 등 순서를 유지한 부분 수열이다.

 

DP의 대표적인 문제 중 하나로, 스트링 편집 거리와 유사하게 접근해 볼 수 있다. 위에서 주어진 예시를 이용하면 "ACAYKP", "CAPCAK"의 LCS를 찾아야 한다. 스트링 편집 거리와 같이 한 문자열은 고정시켜 두고, 나머지 하나의 문자열 중 하나씩 증가시키면서 비교 해 보자. 

 

	A	C	A	Y	K	P
C	0

 

"C"와 "A"의 LCS는 없다. 따라서 0이다.

 

	A	C	A	Y	K	P
C	0	1

 

"C"와 "AC"의 LCS는 "C"이다. 따라서 1이다. 

 

	A	C	A	Y	K	P
C	0	1	1

 

"C"와 "ACA"의 LCS는 "C"이다. 마지막 문자가 달라도, 가장 긴 부분 수열이기 때문에, 이전의 최댓값인 1("C")를 그대로 가져와야 한다. 

 

	A	C	A	Y	K	P
C	0	1	1	1	1	1

 

따라서 마지막 까지 진행하면 다음과 같다. 

 

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1

 

여기서 부터 잘 생각 해 보자. 우리는 DP로 해당 문제를 접근할 것이므로, Recursive Property를 찾아야 한다. "CA"와 "A"의 LCS는 마지막 문자가 동일하므로 1("A")이다. 아직까지는 찾지 못하였다.

 

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1

 

"CA"와 "AC"의 LCS는 1("A")이다. 그렇다면 단순히 마지막 문자가 다른 경우 이전까지의 최댓값 즉, DP[i][j-1]만 고려하면 될까? 아니다. 두 문자열에 공통적인 부분수열이기에, "CA"와 "A"의 LCS와 "C"와 "AC"의 부분수열 모두를 고려하여 최댓값을 가져와야 한다. 이 경우 둘다 1이기에 DP[i][j]는 1이 된다. 

 

$$ DP[i][j] = max(DP[i][j-1] , DP[i-1][j]) \quad , \quad if \; S[i] != S2[j]$$

 

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2

 

"CA"와 "ACA"의 LCS는 2("CA")이다. 이 경우 마지막 문자가 동일한 경우이다. 마지막 문자가 동일한 경우 무조건 +1을 해 줘야 하기 때문에 두 문자열의 마지막 문자를 제외한 최댓값을 가져와야 한다. 따라서 DP[i-1][j-1]에 1을 더해야 정확한 LCS를 계산할 수 있다. 이를 위해서 DP의 첫번째 행과 열은 모두 0이 되어야 한다. 

 

$$ DP[i][j] = 0 \quad , \quad if \; \, i == 0 \; or \; j==0$$

$$ DP[i][j] = DP[i-1][j-1] \, + \, 1 \quad , \quad if \; S[i] == S2[j]$$

 

따라서 위 방법으로 LCS를 구하면 다음과 같다.

 

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

 

---

정답

#include <iostream>
#include <vector>
using namespace std;

string s_S1, s_S2;
int32_t ars32_DP[1001][1001];

int32_t main()
{

	int32_t s32_I, s32_J;

	cin >> s_S1 >> s_S2;
	
	// DP 테이블 구성 시 문자열의 처음 값을 0으로 설정하기 위함
	s_S1 = "0" + s_S1;
	s_S2 = "0" + s_S2;

	for (s32_I = 0; s32_I < s_S1.size(); s32_I++)
	{
		for (s32_J = 0; s32_J < s_S2.size(); s32_J++)
		{
			if (s32_I == 0 || s32_J == 0)
			{
				ars32_DP[s32_I][s32_J] = 0;
			}
			// 두 문자열의 마지막이 동일한 문자인 경우
			else if (s_S1[s32_I] == s_S2[s32_J])
			{
				ars32_DP[s32_I][s32_J] = ars32_DP[s32_I - 1][s32_J - 1] + 1;
			}
			// 두 문자열의 마지막이 동일하지 않은 경우
			else
			{
				ars32_DP[s32_I][s32_J] = max(ars32_DP[s32_I - 1][s32_J], ars32_DP[s32_I][s32_J - 1]);
			}
		}

	}

	cout << ars32_DP[s32_I - 1][s32_J - 1] << endl;
	return 0;
}