[Algorithm]Baekjoon 9251번 :: LCS
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
int dp[1001][1001] = { 0 };
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
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()];
}
|
cs |
코드를 보면 알겠지만 이 문제도 DP로 푸는 문제이다.
일일이 비교하면 당연히 시간초과가 난다.
일단 기본적인 설명은 아래 글이 잘 되어있으니 한번 보는걸 추천.
표로도 예시를 들어놔서 이해하기가 편하다.
https://ongveloper.tistory.com/36
백준 9251 LCS c++
문제 출처 : www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들
ongveloper.tistory.com
두 문자가 같을 때 테이블의 왼쪽 대각선에서 +1을 하는 이유는, 해당 문자를 포함하지않은 상태에서의 DP값에서 +1을 해줘야하기 때문이다. 해당 문자를 포함하지 않은 상태에서의 DP값이 바로 왼쪽대각선의 값이다.
문자가 다를 때 왼쪽이나 위쪽에서 큰 값을 가져오는 이유는, 현재의 문자를 비교하는 과정에서의 바로 이전과정이
DP[i-1][j]와 DP[i][j-1]이기 때문이다. (테이블에서 위와 아래)
이 문제에서의 LCS는 최장 공통 '수열'로 , 공통된부분이 반드시 연속될 필요가 없다.
그렇기 때문에 이전값들을 계속 유지하는게 가능하기 때문에 그냥 제일 큰값을 가져오는게 가능해진다.
사실 이거는 그냥 직접 테이블을 보는게 이해가 제일 빠르다...