최장 공통 부분 수열 (LCS, Longest Common Subsequence) 과 역추적

최장 공통 부분 수열 (LCS, Longest Common Subsequence)문제는 잘알려진 Well-Known 알고리즘으로 간단한 규칙을 통해 구할 수 있습니다. 

A와 B 문장에서 LCS를 구하기 위한 배열 DP[i][j]는 A의 i번째 문자열과 B의 j번째 문자열까지 최대 LCS 길이라고 정의를 하고 DP 배열을 아래와 같이 초기화 합니다.

DP배열 초기

 

이제 2중 포문으로 A[i]와 B[j] 하나씩 비교하면서 DP 배열을 채워줘야합니다. 만약 A[i]와 B[j]가 같은 경우 DP[i][j]를 일단 LCS 길이를 1 늘려줍니다. 

같은 경우

만약 A[i]와 B[j]가 다르다면 LCS 길이는 이전에 구한 LCS중 가장 큰 길이로 채워집니다.

다른 경우

만약 TSET의 첫 T와 TEST의 마지막 T가 만나는 경우를 살펴보겠습니다. 이 경우 A[1]과 B[4]가 만나는 DP[1][4]에 해당하는 LCS를 구해야합니다. 

DP[1][4]는 어떻게 구할 수 있을까요. 두가지 경우로 나눌 수 있는데 

1. TSET의 첫번째 T를 TEST의 4번째 T와 매칭 시킨 LCS 길이를 DP[1][4]로 취한다.

2. TSET의 첫번째 T를 TEST의 4번째 T 이전에 다른 문자열로 매칭 시킨 LCS길이를 DP[1][4]로 취한다.

먼저 첫번째의 경우 TSET의 T를 TEST의 4번째 T와 매칭 시키면, TSET의 첫번째 T 이전의 문자열과 TEST의 4번째 문자 T 이전의 문자열 ( NULL과 TES)의 최대 LCS길이, 즉 DP[1-1][4-1]에 1을 더합니다. 

두번째의 경우 TSET의 첫번째 T는 이전 T와 매칭되었으므로 DP[1][4-1]와 또는 TSET의 T를 이전 T와 매칭 시키지 않은 DP[0][4] 중 긴 LCS 길이를 그래도 DP[1][4]로 취합니다.

두 문자열이 다른 경우도 두번째 경우와 같은 방식으로 구하면 됩니다. 이해를 돕기 위해 아래 그림을 참고해주세요. DP[2][1]의 의미는 TSET의 'TS'와 TEST의 'T' 까지의 누적된 최대 LCS길이를 저장하는 것이기 때문에 S를 T와 매칭할 수 없지만 T가 매칭되는 LCS 길이인 1을 가져옵니다.

LCS를 끝까지 진행하면 DP배열은 다음과같이 채워집니다.

 

답은 DP[4][4] = 3이 되며 TES 또는 TST가 LCS 원래 문자열이 됩니다. 그렇다면 DP 배열을 가지고 어떻게 LCS 문자열을 구할 수 있을까요.

간단한 방법은 DP 배열을 채우는 방법을 거꾸로 진행하면 되는 것입니다. 아래는 TST를 역추적하는 과정입니다. 초록색 원이 LCS로 채택된 문자열이며 빨간색 원은 거쳐가는 원으로 LCS 원래 문자열과 관련이 없습니다.

DP[i-1][j-1] + 1 이 LCS가 된다는 뜻은 A[i]와 B[j]가 매칭되며 이것이 가장 긴 LCS라는 것을 의미하는 것을 다시 떠올려봅시다.

DP[4][4]부터 시작하여 DP[i][j]와 같은 DP[i-1][j] 또는 DP[i][j-1] 가 있다면 둘중 한 곳으로 진행을 합니다. (A[i]와 B[j]가 LCS에 속하지 못하므로)

만약 둘다 다르다면, DP[i][j]에 해당하는 문자열을 스택에 넣고 A[i]나 B[j]가 NULL이 될 때 까지 DP[i-1][j-1]로 이동합니다. (A[i]와 B[j]가 LCS에 속함)

다음은 TET를 역추적 하는 과정입니다. (역시 동일합니다.)

 

아래는 백준에서 풀어볼 수 있는 LCS를 이용한 문제들입니다.

https://www.acmicpc.net/problem/9251

9251번: LCS

https://www.acmicpc.net/problem/9252

9252번: LCS 2

9251번을 재귀로 푼 코드입니다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <memory.h>
#include <math.h>
#include <algorithm>
using namespace std;
int n, m;
string str1, str2;
int dp[1001][1001];
int recv(int s1, int s2) {
	if (s1 == n || s2 == m) {
		return 0;
	}
	int& ret = dp[s1][s2];
	if (~ret) return ret;
	ret = 0;
	if (str1[s1] == str2[s2]) {
		ret = 1 + recv(s1+1,s2+1);
	}
	else {
		ret = max(recv(s1, s2 + 1), recv(s1 + 1, s2));
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(dp, -1, sizeof(dp));
	cin >> str1 >> str2;
	n = str1.length();
	m = str2.length();
	cout << recv(0, 0);
	
}

9252번 코드입니다. dpt는 역추적하는 함수입니다. 위에서 설명된 논리를 그대로 적용한 것입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <memory.h>
#include <string>
using namespace std;
typedef long long ll;
int dp[1001][1001];
int n, m;
string a, b;
int recv(int x, int y) {
	if (x >= n || y >= m) {
		return 0;
	}
	int& ret = dp[x][y];
	if (~ret)return ret;
	ret = 0;
	if (a[x] == b[y]) {
		ret = recv(x + 1, y + 1) + 1;
	}
	ret = max(ret,recv(x + 1, y));
	ret = max(ret,recv(x, y + 1));
	return ret;
}
void dpt(int x, int y) {
	if (x >= n || y >= m) {
		return;
	}
	int res1 = recv(x, y);
	int res2 = recv(x, y + 1);
	int res3 = recv(x + 1, y);
	if (res1 == res2) {
		dpt(x, y + 1);
	}
	else if (res1 == res3) {
		dpt(x + 1, y);
	}
	else {
		cout << a[x];
		dpt(x + 1, y + 1);
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);
	cin >> a >> b;
	n = a.length();
	m = b.length();
	memset(dp, -1, sizeof(dp));
	int ans = recv(0, 0);
	cout << ans <<"\n";
	if (ans) {
		dpt(0, 0);
	}
}