[백준/9252] LCS 2

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/9252

9252번: LCS 2

 

2) 설명

 

2. 풀이

1) 알고리즘

    : DP

 

2) 풀이 설명

두 문자열이 주어질 때 가장 긴 공통 문자열의 길이와 그 문자열을 추출하는 문제.
ex) ABCDEG, BDAEFG 라면 BDEG가 가장 긴 공통 문자열이 되고 길이는 4가 된다.

첫 접근은 DP를 사용해서 공통 문자열의 길이를 구했다.
예를 들어 문자열 A, B가 주어지면 solve(A_idx, B_idx)를 재귀적으로 사용해서 가장 긴 문자열의 길이를 구하는 방식이다.
dp[x][y] 에는 A의 x번째 문자, B의 y번째 문자로부터 만들 수 있는 가장 긴 공통 문자열의 길이를 반환한다.
그러나 이 방식으로는 문자열의 길이는 구해도 어떤 문자열인지 추적하는 일이 너무 힘들었다.
그래서 검색 결과 다른 방식으로 DP를 사용하는 법을 배웠다.

일단 탑다운 방식보다는 바텀업 방식으로 진행해나갔다.

dp[i][j] 는 A의 i번째 문자까지와 B의 j-1번째 문자까지, B의 j번째 문자까지와 A의 i-1번째 문자까지 비교했을 때 가장 긴 공통 문자열의 길이를 의미한다.

그러므로 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])이 된다.

이부분이 상당히 이해하기 까다로웠다.

내가 이해한 바로는 (A[i], B[j-1])로 만들 수 있는 가장 긴 공통 문자열의 길이, (A[i-1], B[j])로 만들 수 있는 가장 긴 공통 문자열의 길이는 (A[i-1], B[j-1])로 만들 수 있는 가장 긴 공통 문자열의 길이와 같거나 1개 더 크기 때문으로 이해했다.

이렇게 다 돌고나면 dp[A의 길이][B의 길이]가 가장 긴 공통 문자열의 길이가 된다.

 

이후 만들어놓은 자취를 따라서 역추적해서 정답 문자열을 추출해내면 된다.

3. 코드

/*
	LCS 2
	DP
	Top-down
    길이만 구할 수 있었다..
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000

using namespace std;

string A = "", B = ""; 
vector<vector<int>> dp(MAX, vector<int>(MAX, -1));

int solve(int A_idx, int B_idx){
	if(A_idx == A.length() || B_idx == B.length())
		return 0;
	if(dp[A_idx][B_idx]>=0)
		return dp[A_idx][B_idx];
	for(int i=A_idx;i<A.length();i++){
		for(int j=B_idx;j<B.length();j++){
			if(A[i] == B[j]){
				dp[A_idx][B_idx] = max(dp[A_idx][B_idx], solve(i+1, j+1)+1);
			}
		}
	}
	return dp[A_idx][B_idx];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> A >> B;
	
	cout << solve(0, 0) << "\n";

	return 0;
}

/*
	LCS 2
	DP
	Bottom-up
*/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 1000

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string A = "", B = ""; 
	cin >> A >> B;
	
	vector<vector<int>> dp(MAX, vector<int>(MAX, 0));

	//길이 구하기
	for(int i=1;i<=A.length();i++){
		for(int j=1;j<=B.length();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]);
			}
		}
	}
	cout << dp[A.length()][B.length()] << endl;
	
	//경로 찾아가기
	string answer = "";
	
	int x = A.length();
	int y = B.length();
	
	while(dp[x][y]>0){
		if(dp[x][y] == dp[x-1][y]){
			x--;
		} else if(dp[x][y] == dp[x][y-1]){
			y--;
		} else {
			answer = A[x-1] + answer;
			x--;
			y--;
		}
	}
	cout << answer << endl;
	return 0;
}

 

4. 느낀점

 - 머리로는 대강 알겠는데 설명하는 게 너무 어렵다. 대강 이해한 게 문제인 것 같다.. 내 생각을 남들이 이해할 수 있도록 표현하는 연습을 하는 것도 중요하니까 어렵더라도 계속 설명하려 노력해야겠다.

 - 단순히 길이만을 구하는 탑다운 풀이에서 벗어나오지를 못했다... 안 될 것 같으면 고집부리지 말고 다른 방식의 풀이도 생각해보자.