[C/C++] 백준 LCS문제 모음 / 백준 9251번, 백준 9252번, 백준 1958번

✏️ 문제 링크

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

9251번: LCS

 

✏️ 문제 설명

✏️ 문제 풀이

기본적인 LCS알고리즘 구현 문제입니다. 

이차원 배열을 만든 후 두 문자열의 길이만큼 for문을 돌려주시면서

A[i-1] == B[j-1]이라면 map[i][j] = map[i-1][j-1] + 1;

A[i-1] != B[j-1]이라면 map[i][j] = max(map[i - 1][j], map[i][j - 1]);

문제 푸는 방식은 dp입니다!

 

✏️ 문제 코드

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

int dp[1001][1001];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string A, B;
	cin >> A >> B;

	for (int i = 1; i <= A.size(); i++) {
		for (int j = 1; j <= B.size(); 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.size()][B.size()];
}

 

 

 

✏️ 문제 링크

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

9252번: LCS 2

 

✏️ 문제 설명

 

✏️ 문제 풀이

기본적인 LCS구현 문제에서 LCS의 길이뿐만 아니라 LCS도 같이 출력하는 문제입니다.

문자열을 출력하기 위해서 getText(int r,int c)함수를 이용하였습니다.

r==0이거나 c==0이라면 return;을, A[r-1] == B[c-1]이라면 path배열에 문자를 추가 후 getText(r-1,c-1)을 호출합니다.

그것도 아니라면 map[r-1][c]와 map[r][c-]중 큰 값에 해당하는 인덱스로 getText()를 호출합니다.

 

✏️ 문제 코드

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

int N;
int dp[1001][1001];
string A, B;
vector<char>path;
void getText(int r, int c);

int main() {

	cin >> A >> B;
	
	for (int i = 1; i <= A.size(); i++) {
		for (int j = 1; j <= B.size(); 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.size()][B.size()] << '\n';
	getText(A.size(), B.size());

	for (int i = path.size() - 1; i >= 0; i--)
		cout << path[i];
}
void getText(int r, int c) {
	if (r == 0 || c == 0)
		return;
	if (A[r - 1] == B[c - 1]) {
		path.push_back(A[r - 1]);
		getText(r - 1, c - 1);
	}
	else {
		if (dp[r - 1][c] > dp[r][c - 1])
			getText(r - 1, c);
		else
			getText(r, c - 1);
	}
}

 

 

 

✏️ 문제 링크

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

1958번: LCS 3

 

✏️ 문제 설명

✏️ 문제 풀이

문장 3개의 LCS의 길이를 출력하는 문제입니다. 처음에는 두 문장을 비교해서 LCS를 찾은 후 이 LCS와 나머지 한 문장을

비교하는 식으로 접근하였는데 이 방식은 처음 LCS를 구할 때 어떤 LCS를 구할 지 모르겠지만 틀린 접근입니다.

그래서 3차원 배열을 사용하여 한 번에 비교를 하였고,배열과 반복문이 2차원에서 3차원으로 바뀐 것 이외에는 코드 구현에서 차이가 없습니다.

 

✏️ 문제 코드

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

int map[101][101][101];
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string A, B, C;
	cin >> A >> B >> C;

	int len1 = A.size();
	int len2 = B.size();
	int len3 = C.size();

	for (int i = 1; i <= len1; i++) {
		for (int j = 1; j <= len2; j++) {
			for (int k = 1; k <= len3; k++) {
				if (A[i - 1] == B[j - 1]&&B[j-1] == C[k - 1])
					map[i][j][k] = map[i - 1][j - 1][k - 1] + 1;
				else
					map[i][j][k] = max(max(map[i - 1][j][k], map[i][j - 1][k]),map[i][j][k-1]);
			}
		}
	}
	cout << map[A.size()][B.size()][C.size()];
}