[LCS(Longest Common Subsequence)] 개념과 예제 문제: LCS1/2_백준 (다이내믹 프로그래밍)

부분 문자열

LIS에서 부분 수열이라는 개념을 다뤘다.
부분 문자열도 같은 개념이다.

어떤 문자열의 부분 문자열은 이 문자열에서 문자의 순서를 바꾸지 않고 몇 개를 지워서 만들수 있는 문자열을 말한다.

예를 들어 a b d c 의 부분 문자열은 다음과 같다.

a
b
d
c
ab
ad
ac
bd
bc
dc
abd
abc
adc
bdc
abdc
(cd는 부분 문자열이 될 수 없다. 원본 문자열에서 순서를 바꾸지 않고는 어떤 문자를 지워도 cd를 만들 수 없다.)

LCS

LCS(Longest Common Subsequence) 문제는 두 문자열 A, B가 주어질 때, A의 부분 문자열이면서 B의 부분 문자열인 문자열 중 가장 긴 것의 길이를 구하는 문제이다.

---

예제 문제: LCS1_백준

LCS1은 탑다운 방식 가능, 재귀의 return이 정수형이라서 가능한듯

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

string S1, S2;
int N1, N2;

int DP[1000][1000];

int reculsive(int s1idx, int s2idx) {
	// 종료 조건
	if (s1idx >= N1)
		return 0;
	
	// DP 활용
	if (DP[s1idx][s2idx] != 0)
		return DP[s1idx][s2idx];

	// 탐색
	int maxLen = 0;

	// 현재 알파벳을 선택하는 경우
	for (int i = s2idx; i < N2; i++) {
		if (S1[s1idx] != S2[i])
			continue;

		maxLen = max(maxLen, 1 + reculsive(s1idx + 1, i + 1));
		break;
	}

	// 현재 알파벳을 선택하지 않은 경우
	maxLen = max(maxLen, reculsive(s1idx + 1, s2idx));

	DP[s1idx][s2idx] = maxLen;
	return maxLen;
}

int solution() {

	return reculsive(0, 0);
}

int main() {
	cin >> S1 >> S2;
	N1 = S1.size();
	N2 = S2.size();

	int answer = solution();
	cout << answer << '\n';
}

참고: https://aerocode.net/269
이 페이지에서 작성자분께서 직접 LCS1 문제에 대해 탑다운 방식과 바텀업 방식의 시간을 비교해주었다.

---

예제 문제2: LCS2_백준

대부분 정답 코드는 바텀업 방식이었다. 탑다운으로 해결해 보았다.
재귀함수에서 문자열을 직접 만들어 반환하는 방식은 문자열 복사 시간으로 인해 시간 초과가 발생한다. 따라서 LCS 문자열을 만드는 로직은 따로 처리해야 한다. 아래 풀이에서 보면, 우선순위 큐와 MAX_CNT 배열(인덱스의 요소는 현재 인덱스부터 최대 x개의 문자열을 만들 수 있다는 의미)을 활용하였다.

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

string S1, S2;
int N1, N2;

int DP[1000][1000];
int MAX_CNT[1000][1000];

struct cmp {
	bool operator() (const pair<int, pair<int, int>>& p1, const pair<int, pair<int, int>>& p2) {
		if (p1.first != p2.first)
			return p1.first < p2.first;	// 내림 차순
		else 
			return p1.second.first > p2.second.first;
		
	}
};

int reculsive(int s1idx, int s2idx) {
	// 종료 조건
	if (s1idx >= N1 || s2idx >= N2)
		return 0;

	// DP 활용
	if (DP[s1idx][s2idx] != 0)
		return DP[s1idx][s2idx];

	// 탐색
	int maxLen = 0;

	// 현재 알파벳을 선택하는 경우
	for (int i = s2idx; i < N2; i++) {
		if (S1[s1idx] != S2[i])
			continue;

		maxLen = max(maxLen, 1 + reculsive(s1idx + 1, i + 1));
		MAX_CNT[s1idx][i] = max(MAX_CNT[s1idx][i], maxLen);
		break;
	}

	// 현재 알파벳을 선택하지 않은 경우
	maxLen = max(maxLen, reculsive(s1idx + 1, s2idx));

	DP[s1idx][s2idx] = maxLen;
	return maxLen;
}

// MAX_CNT 배열을 채우고, LCS의 길이를 구하는 함수
int solution() {

	return reculsive(0, 0);
}

string makeLcsString() {
	// O(n^2*Logn)
	// pair<int, pair<int, int>>
	priority_queue< pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, cmp> pq;
	for (int i = 0; i < N1; i++) {
		for (int j = 0; j < N2; j++) {
			if (MAX_CNT[i][j] == 0)
				continue;

			pq.push({ MAX_CNT[i][j], {i, j} });
		}
	}

	string s = "";
	pair<int, pair<int, int>> p = pq.top(); pq.pop();
	int befores1idx = p.second.first;
	int befores2idx = p.second.second;
	int beforeCnt = p.first;
	s += S1[befores1idx];

	while (!pq.empty()) {
		pair<int, pair<int, int>> p = pq.top(); pq.pop();

		int cnt = p.first;
		int s1idx = p.second.first;
		int s2idx = p.second.second;

		if (cnt >= beforeCnt)
			continue;

		if (befores1idx < s1idx && befores2idx < s2idx) {
			//continue;

			s += S1[s1idx];
			beforeCnt = cnt;
			befores1idx = s1idx;
			befores2idx = s2idx;

			if (cnt == 1)
				break;
		}
	}

	return s;
}

int main() {
	cin >> S1 >> S2;
	N1 = S1.size();
	N2 = S2.size();

	// 1단계: LCS 길이 구하기 및 MAX_CNT 배열 채우기 
	int len = solution();
	cout << len << '\n';	// LCS 길이 출력

	if (len == 0) 
		return 0;
	
	// 2단계: LCS 문자열 하나 찾기
	string s = makeLcsString();


	cout << s << '\n';		// LCS 출력
	return 0;
}