[C++] 백준 9251 - LCS(최장 공통 부분 수열, 동적계획법)

0. 주어진 문제

LCS 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	12692	5366	3962	41.705%

문제

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

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

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

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

예제 입력 1 

ACAYKP
CAPCAK

예제 출력 1 

4

1. 풀이

처음에 도대체 LCS가 무엇인지 위키를 봐도 자세히 이해가 안가서 조금 고생을 하였다.

이런 위키를 대신해서 자세하게 설명해놓은 블로그가 있었는데, 정말 다행스럽게 이 글을 보고 이해를 할 수 있었다.

누가 이런 글을 볼까 의문스럽긴 하지만, 혹시 이 글을 읽을지 모르는 사람을 위해 나도 한번 LCS에 대해 설명을 해보려 한다.

LCS(Longest Common Subsequence)는 내가 생각하기에 와일드카드가 들어간 문자라 생각이 들었다.

위의 예제를 보며 생각을 해보자.

ACAYKP, CAPCAK

이 두 문자열에서 부분 수열을 모두 만들어보자.

1글자 수열

- A

ACAYKP	CAPCAK
??A???, A?????	?A????, ????A?

- K

ACAYKP	CAPCAK
????K?	?????K

- P

ACAYKP	CAPCAK
?????P	??P???

- C

ACAYKP	CAPCAK
?C????	???C??

2글자 수열

- AA

ACAYKP	CAPCAK
A?A???	?A??A?

- AC

ACAYKP	CAPCAK
AC????	?A?C??

- AK

ACAYKP	CAPCAK
A???K?, ??A?K?	?A???K, ????AK

- CA

ACAYKP	CAPCAK
?CA???	CA????, ???CA?

3글자 수열

- ACA

ACAYKP	CAPCAK
ACA???	?A?CA?

- CAK

ACAYKP	CAPCAK
?CA?K?	CA???K, ???CAK

4글자 수열

- ACAK

ACAYKP	CAPCAK
ACA?K?	?A?CAK

위의 글과 같이 수열이 등장하게 된다. 이때, 우리가 찾는 수열은 LCS(최장 공통 부분 수열)이므로, 가장 긴 4글자 수열을 정답으로 갖게 된다.

LCS에 대해 어느정도 이해를 했을 것이라 생각하고, 이제 LCS를 찾는 방식이 어떻게 되는지 알아보자.

LCS는 아래의 점화식과 같이 이루어지는데, 이를 코드로 간단하게 구현해 낼 수 있었다.

메모이제이션을 활용하지 않고 코드를 구현하니 시간초과를 하는 문제가 있었다.

따라서, 메모이제이션을 추가하여 시간초과를 해결할 수 있었다.

2. 소스코드

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

#include<iostream> #include<string> #include<cstring>    //memset활용   std::string a, b;   int cache[1001][1001];   int Max(int a, int b) {     return a > b ? a : b; }   int LCS(int size_of_a, int size_of_b) {     int &ret = cache[size_of_a][size_of_b];     if (ret != -1)         return ret;     if (size_of_a == 0 || size_of_b == 0)         return ret = 0;     else if (a[size_of_a-1] == b[size_of_b-1])         return ret = LCS(size_of_a - 1, size_of_b - 1) + 1;     else if (a[size_of_a-1] != b[size_of_b-1])         return ret = Max(LCS(size_of_a, size_of_b - 1), LCS(size_of_a - 1, size_of_b)); }   int main() {     std::cin >> a >> b;     memset(cache, -1, sizeof(cache));     std::cout << LCS(a.size(), b.size()) << std::endl; } Colored by Color Scripter

cs

3. 문제 출처

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

4. 참고

최장 공통 부분 수열(LCS)

- https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

더 자세한 최장 공통 부분 수열

- https://hsp1116.tistory.com/37

 

와일드카드

- https://namu.wiki/w/%EC%99%80%EC%9D%BC%EB%93%9C%20%EC%B9%B4%EB%93%9C