[LCS(Longest Common Subsequence, 최장 공통 부분 수열)]

01. 문제

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

9251번: LCS

 

02. 코드

#include <iostream>
#include <algorithm>
using namespace std;
const int M = 1000 + 10;

string s1, s2;
int dp[M][M];

int main() {
	cin >> s1 >> s2;

	for (int i = 1; i <= s1.size(); ++i) {
		for (int j = 1; j <= s2.size(); ++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[s1.size()][s2.size()] << endl;
}

 

03. solution

MAP[][]	C(S2[0])	A(S2[1])	P(S2[2])	C(S2[3])	A(S2[4])	K(S2[5])
A(S1[0])	0	1([1, 2])	1	1	1([1, 5])	1
C(S1[1])	1	1	1	2([2, 4])	2	2
A(S1[2])	1	2([3, 2])	2	2	3([3, 5])	3
Y(S1[3])	1	2	2	2	3	3
K(S1[4])	1	2	2	2	3	4([4, 6])
P(S1[5])	1	2	3([6, 3])	3	3	4

 

[LCS 해당 수열 뽑기]

 

01. 문제

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

9252번: LCS 2

 

02. 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
const int M = 1000 + 10;

string s1, s2;
int dp[M][M];
vector<char> res;

int main() {
	//input
	cin >> s1 >> s2;

	//sol_num구하기
	for (int i = 1; i <= s1.size(); ++i) {
		for (int j = 1; j <= s2.size(); ++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[s1.size()][s2.size()] << endl;

	//sol_문자구하기
	int a = s1.size();
	int b = s2.size();
	while (a > 0 && b > 0) { //a==0, b==0 은 종료조건
		if (dp[a][b] == dp[a - 1][b]) {
			--a;
		}
		else if (dp[a][b] == dp[a][b - 1]) {
			--b;
		}
		else {
			res.push_back(s1[a-1]);
			--a; --b;
		}
	}

	//output
	for (int i = res.size() - 1; i >= 0; --i) {
		cout << res[i];
	}
	cout << endl;
}

 

03. solution