[백준] 9251 LCS

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

9251번: LCS

---

최장 공통 부분 수열 (LCS: Longest Common Subsequence) 문제입니다.

 

문제를 처음 보면 모든 가능한 수열을 구해서 비교하는 브루트포스 알고리즘이 떠오를 수 있습니다. 하지만 순열(Permutation) 알고리즘은 O(N!) 시간 복잡도를 가지기 때문에 적절한 해법이 아닌 것 같습니다.

 

그렇다면 다이나믹 프로그래밍으로 풀 수 있을 것 같습니다. 두 문자열의 문자를 하나씩 비교하여 이전의 최대 공통 부분 수열을 기억하고, 그 길이 보다 큰 경우가 나타나면 업데이트 시킬 수 있기 때문입니다.

 

두 문자열의 모든 문자를 살펴봐야하기 때문에 어쩔 수 없이 O(N^2) 시간이 걸릴 것 같으니, 한 번 문제 조건을 살펴보겠습니다.

 

주어진 시간은 1초이니 1억번 연산은 가능할 것 같습니다. 그리고 문자열의 최대 길이는 1000입니다. 1000^2 = 100만이기 때문에 충분합니다. 그러면 DP로 해결해 보겠습니다.

 

문제에 주어진 예시를 통해 최장 공통 부분 수열을 찾아보겠습니다. 

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

 

- 'A'를 기준으로, 3행 4열의 'A'와 동일하니 LCS는 1입니다.

- 'AC'를 기준으로 , 4행 3열에 'C'가 존재하고 'AC'의 부분 수열 중 'C'가 포함되니 1입니다. 그리고 4행 6열에서 'C'가 발견 되었습니다. 이때 'A'를 기준으로하고 3행 5열까지의 LCS를 살펴 보니 1입니다. 그렇다면 'AC' 기준에서 'C'가 발견된 것은 새로운 LCS를 발견한 것이기 때문에 LCS는 2가 됩니다.

- 동일한 알고리즘으로 계속 진행합니다. 결과는 마지막에 볼 수 있듯이 4가 됩니다.

 

 

조금 장황하게 설명하여 다시 말씀드리겠습니다.

3행에서는 'A'라는 문자열과 차례대로 'C', 'CA', 'CAP' .... 을 비교하여 LCS를 구했습니다.

4행에서는 'AC'라는 문자열과 차례대로 'C', 'CA', 'CAP' .... 을 비교하여 LCS를 구했습니다.

 

여기서 'CAPC'라는 문자열과 비교할 때,

 

'AC'는 'A' 문자열에서 'C'가 추가된 것입니다. 

'CAPC'는 'CAP' 문자열에서 'C'가 추가된 것입니다. 

 

따라서 'A', 'CAP'의 LCS에서 1을 더하면 'AC'와 'CAPC'의 LCS가 되는 것 입니다.

 

Python

위 풀이도 충분하지만, 생각해보면 항상 LCS만 기억하고 있으면 되므로 굳이 2차원 배열을 사용하지 않아도 될 것 같습니다. 그러면 좀 더 최적화 해보겠습니다. 

여기서 주의해야할 점은 항상 dp 배열의 마지막 값이 LCS는 아니라는 것 입니다. 왜냐하면, max_len 변수가 매 반복마다 변하고 있고, 항상 최대 값이 할당 되는 것은 아니기 때문입니다.