[C++]백준 - 9252번 문제

9252번: LCS 2 (acmicpc.net)

9252번: LCS 2

 

9252번 : LCS 2

---

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

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

 

입력

---

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

 

 

출력

---

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

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

 

---

 

 

생각해 볼 점

---

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence (velog.io)

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

우선, LCS를 구하는 알고리즘은 위의 링크처럼 2차원 배열 DP를 사용합니다.

 

알고리즘대로 LCS의 길이를 구하고나면, DP의 역추적이 이루어집니다.

 

역추적을 통해 LCS를 찾는 알고리즘 역시 위 링크에서 정말 잘 설명되어있습니다.

(이해가 잘 가는 친절한 설명 감사합니다)

 

코드

---

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

int main() 
{
    string A, B;
	cin >> A >> B;
	
	int A_len = A.length();
	int B_len = B.length();
	
	int **dp = new int*[A_len + 1];
	dp[0] = new int[B_len + 1];
	fill_n(dp[0], B_len + 1, 0);
	
	//다이나믹 프로그래밍, LCS 구하기
	for(int i = 1; i < A_len + 1; i++)
	{
	    dp[i] = new int[B_len + 1];
	    fill_n(dp[i], B_len + 1, 0);
	    
	    
	    for(int j = 1; j < B_len + 1; j++)
	    {
	        if(A[i - 1] == B[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
	        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
	    }
	}
	
	//LCS의 길이
	printf("%d\n", dp[A_len][B_len]);
	
	//역추적
	if(0 < dp[A_len][B_len])
	{
	    string LCS = "";
	    
	    int y = A_len;
	    int x = B_len;
	    while(0 < dp[y][x])
	    {
	        if(dp[y][x] == dp[y-1][x]) 
	        {
	            y--;
	            continue;
	        }
	        else if(dp[y][x] == dp[y][x - 1])
	        {
	            x--;
	            continue;
	        }
	        else
	        {
	            LCS.insert(0, 1, A[y - 1]);
	            y--;
	            x--;
	        }
	    }
	    cout << LCS;
	}
	
	for(int i = 0; i < A_len + 1; i++) delete[] dp[i];
	delete[] dp;

	return 0;
}

 

그 외

---