LCS 2_9251번

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

해결

이 문제를 알기 위해 우선 LCS 알고리즘을 알아야 한다. LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다.

여기서 잠깐! Substring과 Subsequence의 차이를 알아보자. Substring이란 연속적인 부분 문자열이고 Subsequence란 연속적이지 않은 부분 문자열이다. 예를 들어보자.

ABCD, ABEC

Substring : ABCD, ABEC -> AB
Subsequence : ABCD, ABEC -> ABC
두 문자열 간의 Substring과 Subsequence가 이처럼 다르다는 것을 알 수 있다.

LCS는 두 문자열 간의 최장 공통 'Subsequence'를 구하는 것이다. 이제 그 과정을 알아볼 것이다.

일단 두 문자열 내에서 나올 수 있는 부분문자열 간의 최장 공통 부분 수열의 길이를 담고 있는 이차원 배열이 필요하다. 두 문자열이 갖고 있는 각 문자가 서로 같은지 같지 않은지에 따라 배열에 채워지는 값이 달라진다. 문제에서 ACAYKP와 CAPCAK의 LCS에 대한 예시를 주었으니 이를 가지고 살펴볼 것이다.

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

일단 이 상태가 기본이다. 현재 채워진 0은 현재까지의 부분 문자열과 공백 문자열 간의 Subsequence의 길이를 담은 것이라고 봐도 될 것 같다. 이제 이어서 살펴볼 예정이다.

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

현재 파란색으로 표시한 0은 A와 C 간의 Subsequence가 없다는 것(두 문자열 간의 Subsequence의 길이가 0)을 의미하고 빨간색으로 표시한 1은 AC와 C 간의 Subsequence가 있다(두 문자열 간의 Subsequence는 C이며 그 길이가 1)는 것을 뜻한다.

한 칸 더 진행해보자.

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

이는 문자열 ACA와 C 간의 Subsequence의 길이가 1이라는 것을 내포하고 있다. 본격적으로 원리를 알아보기 위해 조금 진도를 빼볼 예정이다.

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

ACAYKP와 C 사이의 Subsequence는 구한 상태이고 이제 ACAYKP와 CA 간의 Subsequence를 구하는 과정 중 하나인 ACA와 CA 간의 Subsequence의 길이를 구하는 과정이다. 현재 ACA의 마지막 'A'과 CA의 'A'가 같은 문자이다.

	0	A	C	A
0	0	0	0	0
C	0	0	1	1
A	0	1	1	2

빨간 색으로 표시한 2의 왼쪽 위쪽 방향 대각선 노란색 1에 1을 더한 값이다. 그 이유는 노란색 1은 AC와 C 사이에 최대 Subsequence의길이가 1이라는 의미이며 각 문자열에 공통문자 A가 붙어 ACA와 CA가 되면 그 길이가 1 증가하기 때문이다.

즉, 두 문자열 간의 특정 문자가 같으면 왼쪽 위쪽 대각선의 값에 1을 더하면 된다.

이제 좀 더 진행해보자.

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

현재, 빨간 색으로 위치한 2는 AC와 CAPC의 Subsequence의 최대 길이가 2라는 뜻이다. 지금 AC의 'C'와 CAPCA의 마지막 'A'는 서로 다른 문자이다. 이럴 경우에는 어떻게 해야할까?

	0	A	C
0	0	0	0
C	0	0	1
A	0	1	1
P	0	1	1
C	0	1	2
A	0	1	2

여기서는 값의 변화가 일어나면 안된다. 그런데, 그 값의 기준은 어디서 나오는 것일까? 본인 위치의 왼쪽 칸과 위쪽 칸을 확인해보면 된다.

왼쪽의 1 : A와 CAPCA 간의 subsequence는 A로 최대 길이는 1이다.
위쪽의 2 : AC와 CAPC 간의 subsequence는 AC로 최대 길이는 2다.

이 두 값 중 더 큰 값을 적용시키면 된다. 말 그대로 '최대' 길이이기 때문이다.

즉, 두 문자열 간의 특정 문자가 다르면 본인의 왼쪽과 위쪽 칸을 따진 후 더 큰 값을 담는다.

이제 이 배열을 채우면...

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

이렇게 된다. 여기서 Substring의 최대 길이를 구하고자 하면 배열의 우측 맨 아래쪽 값을 보면 된다. 이 테이블에서는 4가 된다.
(ACAYKP와 CAPCAK의 Substring은 ACAK로 길이는 4다.)

이제 Substring 자체를 구하는 방법을 알아볼 예정이다. 배열까지 잘 구했으면 이거는 이제 쉽다. 아까 거쳐왔던 과정을 거꾸로 진행해주기만 하면 된다. 우측 하단에서 탐색을 시작한다.

1) 왼쪽을 탐색한다. 본인과 값이 같으면 그 방향으로 이동한다.
2) 왼쪽과 값이 다르면 위쪽을 탐색한다. 본인과 값이 같으면 그 방향으로 이동한다.
3) 위쪽 또한 값이 다르면 왼쪽 위쪽 대각선 방향으로 이동한다. 이동하면서 배열 상에서 현재 위치의 행과 열에 해당하는 문자를 기억해두면 된다. = 스택에 쌓아주면 된다.
(왼쪽과 위쪽 모두 본인과 다르다는 것은 본인 위치의 문자열이 두 문자열 간 겹치는 문자라는 것을 나타낸다.)
4) 1) ~ 3) 과정을 본인 위치의 값이 0이 될 때까지 반복한다.

이 과정에서 3)에 걸리는 문자를 기억해뒀다가 나중에 역순으로 읽어주기만 하면 된다. (스택에 쌓인 문자들을 전부 꺼내면서 읽어주면 된다.)

이제 코드를 살펴볼 차례이다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int dp[1001][1001];
stack<char> s;

int main() {
	string str1;
	string str2;
	cin >> str1; // 기준
	cin >> str2; // 대상

	int size1 = str1.size();
	int size2 = str2.size();

	for (int i = 0; i <= size2; i++) {
		for (int j = 0; j <= size1; j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 0;
			}
			else {
				if (str1.at(j - 1) == str2.at(i - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} // 두 문자가 같을 경우
				else {
					if (dp[i - 1][j] > dp[i][j - 1]) {
						dp[i][j] = dp[i - 1][j];
					}
					else {
						dp[i][j] = dp[i][j - 1];
					}
				} // 두 문자가 다를 경우
			}
		}
	}

	cout << dp[size2][size1] << endl;

	int idx1 = size1;
	int idx2 = size2;
	
	while (dp[idx2][idx1] != 0) {
		if (dp[idx2][idx1 - 1] == dp[idx2][idx1]) {
			idx1--;
		} // 왼쪽 이동
		else if (dp[idx2 - 1][idx1] == dp[idx2][idx1]) {
			idx2--;
		} // 위쪽 이동
		else {
			s.push(str1.at(idx1 -1));
			idx1--;
			idx2--;
		}
	}

	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}

	return 0;
}

지금까지 알아본 과정을 그대로 코드에 담았으며 코드 해석이 그리 어렵지 않기 때문에 자세한 설명은 생략하였다. 문자열의 인덱스는 0부터 시작하니 헷갈리지 않게 코드를 짜는 것과 최대 길이를 가진 Subsequence를 구하기 위해서는 스택을 사용한다는 점만 유념하면 될 것 같다.