[백준] 9251,9252,1958 LCS,LCS2,LCS3 최장 공통 부분수열

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

두 string A,B를 입력받을때,
A[i]와 B[j]를 비교합니다. (i: 1~A.length, j:1~B.length)
    만약 A[i-1]와 B[j-1]가 같으면,
         dp[i][j] : "A[i-1]까지와 B[j-1] 까지 비교해 만들 수 있는 가장 긴 공통수열의 길이 " 는
         dp[i-1][j-1] + 1 ( A[i-2]까지와 B[j-2]까지 비교했을 때 만들 수 있는 가장 긴 공통수열의 길이 + 1 )
    만약 A[i-1]와 B[j-1]가 다르다면
         dp[i][j]는 dp[i-1][j] 와 dp[i][j-1]중 큰 값입니다. : A[i-2],B[j-1] 와 A[i-1],B[j-2]로 만들 수 있는 공통수열의 길이 중,           더 큰 값입니다.

 

LCS 1 입니다.

#include<iostream>
#include<algorithm>
using namespace std;
int dp[1001][1001], i, j; 
int main() {
	string a, b;
	cin >> a >> b;
	for (i = 1; i <= a.size(); i++)
		for (j = 1; j <= b.size(); j++) 
        //삼항연산자를 사용했습니다
			a[i - 1] == b[j - 1] ? dp[i][j] = dp[i - 1][j - 1] + 1 : dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
	cout << dp[i - 1][j - 1] << "\n";

 

 

LC2의 공통수열의 길이 뿐만이 아니라, 공통수열이 뭔지 출력하는 부분입니다.

	i--, j--;
	string ans;
	while (dp[i][j]) {
		if (dp[i][j] != dp[i - 1][j] && dp[i][j] != dp[i][j - 1]) {
			ans.push_back(a[i-1]);
			i--;
			j--;
		}
		else if (dp[i][j] == dp[i - 1][j]) {
			i--;
		}
		else {
			j--;
		}
	}
	reverse(ans.begin(), ans.end());
	cout << ans;

dp[i][j]가 0이 아니면 계속 반복합니다 i,j는 왼쪽 맨 아래, i:A.length, j:B.length 에서 시작합니다.
   만약 dp[i][j]가 dp[i-1][j],dp[i][j-1]과 모두 다르다면, 그 위치는 갱신된 위치이므로, a[i-1]를 push하고, i--;j--; 이동 합     니다.

   만약 dp[i-1][j]나 dp[i][j-1]중 하나라도 같으면, 그 위치가 갱신된 위치일 수 있으므로, 그 위치로 i-- or j--로 이동합       니다.

 

LCS3

만약 문자열이 3개로, 3문자열의 LCS를 구하는 문제의 알고리즘은 똑같습니다.

#include<iostream>
#include<algorithm>
using namespace std;
int dp[101][101][101], i, j, k, ans;
int main() {
	string a, b, c;
	cin >> a >> b >> c;
	for (i = 1; i <= a.size(); i++){
		for (j = 1; j <= b.size(); j++) {
			for (k = 1; k <= c.size(); k++) {
				if (a[i - 1] == b[j - 1] && a[i - 1] == c[k - 1]) {
                //만약 3개의 문자가 모두 같다면,
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
					ans = max(ans, dp[i][j][k]);
				}
				else {
                //그게 아니라면
					dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k]);
					dp[i][j][k] = max(dp[i][j][k], dp[i][j][k - 1]);
				}
			}
		}
	}
	cout << dp[i - 1][j - 1][k-1] << "\n";

}