[DP] LCS (Longest Common Subsequence)

LCS ( Longest Common Subsequence )

두 문자열을 입력 받고, 그 중에서 최장 공통 부분 수열을 찾는 문제이다.
 

-원리

두 문자열 X(x1, x2, x3...), Y(y1, y2, y3...)가 있을 때 가장 마지막 원소부터 비교해본다.
같은 경우, 그 다음 시도부터는 해당 원소를 빼고 생각해도 되므로 각 문자열 크기가 1씩 줄어든다.
다른 경우, X의 마지막 원소랑 Y 원소 전체랑 비교하거나 반대로 Y의 마지막 원소랑 X 원소 전체랑 비교하여 각각 문자열의 크기를 줄여나간다. DP는 크기를 줄이는 게 목적이므로 이런 식으로 subproblem을 구상하는 것이다.

 
위 경우의 수를 점화식으로 표현하면 다음과 같다.
 
 

-점화식

i == X 문자열의 index / j == Y 문자열의 index / c == 해당 문자까지의 LCS 개수 저장(optimal value)

 
 

-DP 과정 (Bottom-up approach)

X: GEGGGA
Y: FGGAEC
위와 같은 두 문자열에서 점화식대로 LCS를 찾게 되면 아래와 같이 나오게 된다. 초기에 index가 0인 것들은 전부 0으로 초기화를 해준 상태에서 시작한다. X[i]와 Y[j]를 비교해야 하는데, 여기서 주의할 점은 문자열의 길이보다 DP의 index길이가 한 칸 더 길다는 것이다. 즉 처음에 G랑 F를 비교할 때 해당 결과가 저장되는 건 DP[1, 1]이지만 문자열 배열 관점으로보면 X[0], Y[0]이다. (따라서 코드로 작성할 때도 점화식 그대로 작성하면 결과가 달라진다... 코드에서는 X[i-1]==Y[j-1]로 줄여서 비교해줘야 한다.)
비교를 해서 문자가 같으면 왼쪽 대각선의 값 + 1로 해서 저장하고(여기까지 문자가 같으니 LCS길이에 추가한다는 뜻), 문자가 다르다면 왼쪽과 위쪽의 값중 max값을 가져와서 저장한다.(이전 값들 중 뭐가 더 큰지)
최종적으로 맨 마지막 칸을 구하면 그 값이 LSC의 길이가 된다.

 

-Code

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

int C[1001][1001]; //optimal value

int main()
{
	string X, Y;
	cin >> X >> Y;
	
	int m = X.length();
	int n = Y.length();

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (X[i-1] == Y[j-1]) { //실제 문자열은 C보다 한칸 작음
				C[i][j] = C[i - 1][j - 1] + 1;
			}
			else {
				C[i][j] = max(C[i - 1][j], C[i][j - 1]);
			}
		}
	}

	cout << C[m][n];

	return 0;
}

출력 결과도 풀이와 같이 3으로 나옴

 
 

-Time Complexity

코드 상에서, 이중 for문으로 되어 있는데 각 길이가 다를 수 있기 때문에 O(n*m)이 된다. (예제처럼 같은 길이면 O(n^2))