[백준] #9252 LCS2(Longest Common Subsequence) - (DP)

문제

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

9252번: LCS 2

목표

두개의 문자가 주어졌을때 두 문자의 부분수열중 최장길이의 부분수열을 구하는 문제

풀이

dp를 사용하여 각 구간마다 최장부분수열의 길이를 저장시켜놓는다.

사진에서 동그라미 친 부분은 두 문자열의 부분문자가 같은 구간 => dp값이 1증가해야한다.

점화식

dp[i][j] = if (s1[i] == s2[j])   dp[i-1][j-1] + 1;

         = else                   max( dp[i-1][j], dp[i][j-1] );

 

코드

1. 재귀로구현

#include <iostream>
#include <cstring>
#include <stack>
#define MAX 1001

using namespace std;

//dp[i][j]: i행 j열위치에서 확인한 LCS의 최대값
int dp[MAX][MAX];
string str1;
string str2;
stack<char> s;

//지나간 dp배열값은 모두 0이상의 값으로 초기화됨 => 트래킹 가능
int func(int i, int j) {
	//문자열을 비교할수있는 범위를 넘어가면 0으로 초기화
	if (i <= 0 || j <= 0)
		return dp[i][j] = 0;
	int &ref = dp[i][j];
	if (ref != -1)
		return ref;
	//문자열의 문자가 서로 같은경우 대각선의 dp값 + 1
	if (str1[i-1] == str2[j-1]) {
		ref = func(i-1, j-1) + 1;
	}
	//문자열의 문자가 서로 다른경우 dp의 왼쪽, 위쪽중 최대값을 가짐
	else {
		ref = max(func(i, j-1), func(i-1, j));
	}
	return ref;
}
int main() {
	cin >> str1 >> str2;
	memset(dp, -1, sizeof(dp));
	cout << func(str1.length(), str2.length()) << '\n';

	// cout << '\n' << '\n';
	// for (int i=0; i<=str1.length(); i++) {
	// 	for (int j=0; j<=str2.length(); j++) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << '\n';
	// }

	//트래킹작업
	//1. 왼쪽비교, 2. 위쪽비교 => 값이 현재값과 같다면 LCS문자열이 아니다.
	//3. 대각선비교 => 값이 현재값-1 이라면 LCS문자열이다.
	int i = str1.length();
	int j = str2.length();
	while (i>0 && j>0) {
		int tmp = dp[i][j];
		//왼쪽값과 같다면 왼쪽이동
		if (tmp == dp[i][j-1]) {
			--j;
			continue;
		}
		//위쪽값과 같다면 위쪽이동
		if (tmp == dp[i-1][j]) {
			--i;
			continue;
		}
		//대각선값+1값과 같다면 대각선이동
		if (tmp-1 == dp[i-1][j-1]) {
			--i; --j;
			s.push(str1[i]);
			continue;
		}
		return 0;
	}
	//추적한 값 출력
	while (!s.empty()) {
		cout << s.top();
		s.pop();
	}
	// cout << '\n' << '\n';
	// for (int i=0; i<=str1.length(); i++) {
	// 	for (int j=0; j<=str2.length(); j++) {
	// 		cout << dp[i][j] << " ";
	// 	}
	// 	cout << '\n';
	// }
}

 

2. 반복으로구현

#include <iostream>
#include <vector>
#include <stack>
#define MAX 1001

using namespace std;

string s1;
string s2;
int dp[MAX][MAX];
stack<char> s;

void func() {
    int len1 = s1.length();
    int len2 = s2.length();

    for (int i=1; i<=len1; ++i) {
        for (int j=1; j<=len2; ++j) {
            if (s1[i-1] == s2[j-1]) 
                dp[i][j] = dp[i-1][j-1] + 1;
            else 
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[len1][len2] << '\n';

    while (dp[len1][len2] != 0) {
        if (dp[len1][len2] == dp[len1][len2-1])
            len2--;
        else if (dp[len1][len2] == dp[len1-1][len2])
            len1--;
        else {
            s.push(s1[len1-1]);
            len1--;
            len2--;
        }
    }
    while (!s.empty()) {
        cout << s.top();
        s.pop();
    }
}
int main() {
    cin >> s2 >> s1;
    func();
}