[C++] 백준 9251: LCS

Cyan·2024년 2월 25일

코딩 테스트

목록 보기

106/166

백준 9251: LCS

문제 요약

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

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

입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

문제 분류

다이나믹 프로그래밍
문자열

문제 풀이

2차원 배열의 DP문제이다. 위의 문자열을 a, 밑의 문자열을 b라고 했을 때, dp[i][j]는 a의 0~i구간 문자열과 b의 0~j구간 문자열의 LCS가 된다. 이는 2가지 구조로 풀 수 있다.

가령 다음의 예제 입력 예시를 보자. DP배열은 다음과 같고, 우선 0번 행과 0번 열은 모두 0으로 초기화 되어야한다.

-	C	A	P	C	A	K
0	0	0	0	0	0	0
A
C
A
Y
K
P

이후 0~1인, 문자열 "A"와 각 열까지의 b문자열을 비교하여 연산한다.

-	C	A	P	C	A	K
0	0	0	0	0	0	0
A	0	1	1	1	1	1
C
A
Y
K
P

이후 0~2인, 문자열 "AC"와 각 열까지의 b문자열을 비교하여 연산한다.

-	C	A	P	C	A	K
0	0	0	0	0	0	0
A	0	1	1	1	1	1
C	1	1	1	1	2	2
A
Y
K
P

그 다음 행도 계속해서 마찬가지로 채워 넣으면 다음의 배열이 완성된다.

-	C	A	P	C	A	K
0	0	0	0	0	0	0
A	0	1	1	1	1	1
C	1	1	1	1	2	2
A	1	2	2	2	3	3
Y	1	2	2	2	3	3
K	1	2	2	2	3	4
P	1	2	2	2	3	4

즉 i(1~a.length())와 j(1~b.length())에 대해

dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] + (a[i - 1] == b[j - 1])) 과 같다.

즉, dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + (a[i - 1] == b[j - 1]) 중의 최댓값이다.

또한 그 최댓값은 언제나 dp[a.length()][b.length()]일 것이다.

2번째 경우는 첫 번째 행과 열의 0을 전부 없애버리는 것이다. 그러면 dp배열은 다음과 같아진다.

-	C	A	P	C	A	K
A	0	1	1	1	1	1
C	1	1	1	1	2	2
A	1	2	2	2	3	3
Y	1	2	2	2	3	3
K	1	2	2	2	3	4
P	1	2	2	2	3	4

풀이 코드

첫 번째 풀이

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int dp[1001][1001];
string a, b;

int main()
{
	cin >> a >> b;
	for (int i = 1; i <= a.length(); i++) {
		for (int j = 1; j <= b.length(); j++)
			dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] + (a[i - 1] == b[j - 1]));
	}
	cout << dp[a.length()][b.length()];
	return 0;
}

두 번째 풀이

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

int dp[1001][1001];
string a, b;

int main()
{
	cin >> a >> b;
	dp[0][0] = a[0] == b[0];

	for (int i = 1; i < b.length(); i++)
		dp[0][i] = max(dp[0][i - 1], (a[0] == b[i]) ? 1 : 0);
	for (int i = 1; i < a.length(); i++)
		dp[i][0] = max(dp[i - 1][0], (a[i] == b[0]) ? 1 : 0);
	for (int i = 1; i < a.length(); i++) {
		for (int j = 1; j < b.length(); j++)
			dp[i][j] = max(max(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1] + (a[i] == b[j]));
	}
	cout << dp[a.length() - 1][b.length() - 1];

	return 0;
}