4-(1)Dynamic Programming 3)Longest Common SubSequence

이 단원에서는 Longest Common SubSequence문제와 그 Dynamic Programming 해법에 대해 알아본다.

LCS문제를 소개하기 위해  Sequence라는 것을 먼저 정의하자  Sequence는 다음과 같이 주어진 순서있는 집합이다.

X=<A,B,C,B,D,A,B>

이 때 X의 subsequence는 다음과 같이 X에 속하는 멤버들을 골라서 만드는 sequence를 얘기한다.

<B,C,D,B>, <A,B,A,B>

 

이 때 LCS문제는 다음과 같이 주어진다.

Q:X=<x₁,...,x_m>, Y=<y₁,...,y_n>의 common subsequence 중 그 길이가 가장 긴 Subsequence는?

input: X,Y

output: LCS Z

 

이 문제는 DP로 풀리는데, 다음과 같은 Thm을 생각해볼 수 있기 때문이다.

Thm15.1

X와 Y에서 LCS Z가 주어졌을때

(1) x_m=y_n인 경우: z_k=x_m=y_n

(2) x_m!=y_n인 경우 & z_k!=x_m: z_k=LCS of X_m-1& Y_n

(3) x_m!=y_n인 경우 & z_k!=y_n: z_k=LCS of X_m& Y_n-1

따라서 recursive solution을 다음과 같이 구성할 수 있다.

C[i,j]를 X_i와Y_j의 LCS 길이를 담은 해라고 했을 때,

C[i,j]=        0       when i=0 or j=0

               c[i-,j-1]+1 when x_i=y_j 

               max(C[i,j-1],C[i-1,j]) when x_i!=y_j

그리고 x_i=y_j일 때 LCS멤버가 추가된 것이므로 LCS멤버구성을 위해 b[i,j]를 이용해 LCS를 찍어준다.

밑은 이것을 Bottom-up방식으로 구현한 Function과 Testcode를 포함한 코드이다. 

 

#include<iostream>
using namespace std;
const int UPPERLEFT=100;
const int UPPER = 1000;
const int LEFT = 10000;

int** LCS(char* X, int x_size, char* Y, int y_size,int **b) {
	int** c = new int*[x_size + 1];
	for (int i = 0; i <= x_size; i++)
		c[i] = new int[y_size + 1];
	//c->LCS의 length저장
	//b->화살표의 방향 저장
	//c[i][j]: Xi와 Yj의 LCS 길이 저장
	for (int i = 0; i <= x_size; i++)
		c[i][0] = 0;
	for (int j = 0; j <= y_size; j++)
		c[0][j] = 0;
	//최종 원하는 거: c[x_size][y_size]
	for (int i = 1; i <= x_size; i++) {
		for (int j = 1; j <= y_size; j++) {
			if (X[i-1] == Y[j-1]) {	//X의 i번째문자는 X[i-1]에 있기 때문에
				c[i][j] = c[i - 1][j - 1] + 1;
				b[i][j] = UPPERLEFT;
			}
			else if (c[i][j - 1] > c[i - 1][j]) {
				c[i][j] = c[i][j - 1];
				b[i][j] = LEFT;
			}
			else{
				c[i][j] = c[i - 1][j];
				b[i][j] = UPPER;
			}
		}
	}
	return c;
}

void printLCS(char* X, int i, char* Y, int j, int** b) {
	if (i == 0 || j == 0) return; //basis case
	if (b[i][j] == UPPERLEFT) { //xi==yj인 경우, LCS에 포함되는 경우임, 
		//순서가 recursive에서 거꾸로 출력해야 하니까 함수call-print가 되어야함.
		printLCS(X, i - 1, Y, j - 1, b);
		cout << X[i];
	}
	else if (b[i][j] == UPPER) { //i가 줄어든 경우, 즉 subLCS가 X쪽에 있었던 경우
		printLCS(X, i - 1, Y, j, b);
	}
	else {	//j가 줄어든 경우, 즉 subLCS가 Y쪽에 있었던 경우
		printLCS(X, i, Y, j - 1, b);
	}
}
int main() {
	char X[] = "ABCBDAB";
	char Y[] = "BDCABA";
	int x_size = 7;
	int y_size = 6;
	int** b = new int*[x_size + 1];
	for (int i = 0; i <= x_size; i++)
		b[i] = new int[y_size + 1];
	int** c = LCS(X, x_size, Y, y_size, b);
	cout << "LCS length:" << c[x_size][y_size] << endl;
	cout << "LCS of " << X << " and " << Y << " is ";
	printLCS(X, x_size, Y, y_size, b);
	return 0;
}

b를 이용해 LCS멤버를 print해주는 printLCS함수도 추가하였는데, 이것은 사실 C배열만 갖고 있어도 다시 찍어줄 수 있다. 우리는 생각해보면, BottomUp방식으로 했기 때문에, 함수 자체에서 LCS를 print해줄 수는 없지만 LCS를 Print하는데는 다음과 같은 원칙을 생각해보면 된다. 위의 재귀해를 다시 가져와보자.

C[i,j]=        0       when i=0 or j=0

               c[i-,j-1]+1 when x_i=y_j 

               max(C[i,j-1],C[i-1,j]) when x_i!=y_jssssssss

그러면 우리가 LCS에 멤버를 추가하는건 두번째 경우로 xi=yj일 때 뿐이다.

만약, 이것을 top-down방식으로 풀고 두번째 경우를 볼 때마다 특정 stack에 이 멤버를 추가한다면 이 stack을 pop하는 것만으로도 LCS를 구성할 수 있게 되리란 것을 예상해볼 수 있다. 그런 의미에서 b배열은 bottom-up방식으로 문제를 해결하면서 top-down방식으로 문제를 풀 때에 어떻게 해가 재귀적으로 풀리게 되리란 것을 tracing해놓은 변수가 될 것이다.

 

그리고 책에서 Optimal Substructure성질에 대한 언급이 있는데, 핵심은 문제를 substruct화 할 수 있다는 것이 아니다. 핵심은 sub문제간 독립성이다. Longest simple path가 DP로 풀 수 없는 대표적인 문제로 꼽힌다.