[백준 9252번 C/C++] LCS 2

 

[백준 9252번 C/C++] LCS 2

 

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

9252번: LCS 2

---

 

해결전략

 

LCS Longest 

다이나믹 프로그래밍 Dynamic Programming

슬라이딩 윈도우 알고리즘 Sliding Window Algorithm

 

 

---

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <vector>
using namespace std;

string a, b;
string answer;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> a >> b;
	int aSize = a.size(); // 첫번째 주어진 문자열 길이
	int bSize = b.size(); // 두번째 주어진 문자열 길이
	vector<vector<pair<int, string>>> dp(aSize + 1, vector<pair<int, string>>(bSize + 1, {0, ""}));

	for (int i = 1; i <= aSize; i++) {
		for (int j = 1; j <= bSize; j++)
		{
			if (a[i - 1] == b[j - 1]) {
				dp[i][j].first = dp[i - 1][j - 1].first + 1;
				dp[i][j].second = dp[i - 1][j - 1].second + a[i - 1];				
			}
			else {
				dp[i][j].first = max(dp[i - 1][j].first, dp[i][j - 1].first);
				if (dp[i - 1][j].first > dp[i][j - 1].first) dp[i][j].second = dp[i - 1][j].second;
				else dp[i][j].second = dp[i][j - 1].second;
			}
		}
	}

	cout << dp[aSize][bSize].first << "\n";
	cout << dp[aSize][bSize].second << "\n";

	return 0;
}

 

---

 

두번째 시도한 코드 -  92%시간 초과

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

    string a, b;
	cin >> a >> b;
	int aSize = a.size();
	int bSize = b.size();

	vector<pair<int, string>> dp(bSize + 1, { 0, "" });
	vector<pair<int, string>> dp2(bSize + 1, { 0, "" });

	for (int i = 1; i <= aSize; i++) {
		for (int j = 1; j <= bSize; j++)
		{
			if (a[i - 1] == b[j - 1]) {
				dp2[j].first = dp[j - 1].first + 1;
				dp2[j].second = dp[j - 1].second + a[i - 1];
			}
			else {
				if (dp2[j - 1].first > dp[j].first) {
					dp2[j].first = dp2[j - 1].first;
					dp2[j].second = dp2[j - 1].second;
				}
				else {
					dp2[j].first = dp[j].first;
					dp2[j].second = dp[j].second;
				}
			}
		}
		dp = dp2;
	}

	cout << dp[bSize].first << "\n";
	cout << dp[bSize].second << "\n";

	return 0;
}

 

슬라이딩 윈도우 알고리즘 기법을 사용하였다.

2차원 dp 테이블 대신 1차원 dp 백터 2개를 사용하여 메모리 사용량을 줄였다. 각 문자열의 위치마다 계산된 LCS의 길이와 해당 LCS를 저장하게 된다.

이전 행의 계산 결과는 dp 백터에, 현재 행의 계산 결과는 dp2 백터에 저장된다. 각 행의 계산이 끝날 때마다 dp 백터는 dp2 백터의 값으로 업데이트되며, dp2 백터는 다음 행의 계산을 위해 초기화된다. 

 

 

---

 

정답 코드

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	string a, b;
	cin >> a >> b;
	int aSize = a.size(); // 첫번째 주어진 문자열 길이
	int bSize = b.size(); // 두번째 주어진 문자열 길이
	vector<vector<int>> dp(aSize + 1, vector<int>(bSize + 1, 0));

	// LCS를 dp[][] 표 형태로 만들어 LCS의 길이 구하기. dp[aSize][bSize]가 길이 최대값
	for (int i = 1; i <= aSize; i++) {
		for (int j = 1; j <= bSize; j++)
		{
			if (a[i - 1] == b[j - 1]) // 두 문자가 같을 경우 대각선 위(dp[i - 1][j - 1]) 값에 1을 더함
				dp[i][j] = dp[i - 1][j - 1] + 1;
			else // 두 문자가 다를 경우 왼쪽(dp[i - 1][j])과 위(dp[i][j - 1]) 중 큰 값 선택
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	cout << dp[aSize][bSize] << "\n"; // LCS의 최대 길이 출력


	// LCS 문자 구하기. dp[][] 테이블을 역으로 추적하여 LCS를 구함
	string answer;
	for (int i = aSize; i >= 1; i--) {
		for (int j = bSize; j >= 1; j--)
		{
			if (dp[i][j] == dp[i - 1][j]) { // 바로 위 dp값이 같으면 현재 열 값을 유지
				bSize = j;
				break;
			}
			else if (dp[i][j] == dp[i][j - 1]) continue; // 바로 왼쪽 dp값이 같으면 다음 열로 이동
			else // 두 조건이 아니면 현재 문자를 LCS에 추가하고 대각선 위로 이동
				answer = a[i - 1] + answer;
		}
	}

	cout << answer << "\n"; // LCS 출력

	return 0;
}

 

 

 LCS 길이와 문자열을 구하는 DP 테이블 생성 과정

• 길이 계산: 입력된 문자열 a, b에 대해 각각의 길이를 구한 후 vector<vector<int>> dp를 사용해 테이블을 초기화한다. 이때의 각 셀에는 두 문자열의 서브시퀀스 중 최장 길이를 저장
• 테이블 채우기: 문자열 a와 b를 비교하여 같은 문자가 나올 경우 대각선 위의 값에 1을 더해 새로운 값으로 업데이트하한다. 만약 다른 문자일 경우, 이전의 최대값을 가져와 업데이트한다.

 

 

최장 공통 부분 수열(LCS) 추출

• 역추적: dp 테이블을 역으로 추적하면서 LCS 문자열을 구한다. 만약 현재 dp 값과 바로 위 값이 같다면, 해당 열의 값을 유지한다. 바로 왼쪽 값과 같으면 다음 열로 이동한다.
• LCS 문자열: 두 조건에 해당하지 않는 경우에는 해당 문자를 LCS 문자열에 추가하고, 대각선 위 셀로 이동