[백준] 9251번 LCS (Longest Common Subsequence)

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

9251번: LCS

이 문제를 풀기 전에 알아야 할 개념 : Dynamic Programming

 

LCS란?

LCS란 두 문자열 str1과 str2가 있다고 할 때, 공통된(Common) 부분 수열(Substring) 중, 가장 긴 것(Longest)을 의미한다. 여기서 Subsequence의 개념을 명확히 할 필요가 있는데, 원래 문자열의 글자를 몇 개 선택해서 원래 문자열의 순서에 맞게 나열한 것을 말한다. 예를 들어 Algorithm에서 gom은 Algorithm이라는 문자열에서 g, o, m이라는 문자를 선택해 원래 문자열의 순서대로 나열한 것이다. Subsequence는 Substring과도 혼동되는데, Substring은 한 문자를 선택했을 때, 인접한 문자들만 선택할 수 있다. 예를 들어 Algorithm에서 Algo는 인접한 문자들끼리만 선택했으니 Substring에 해당한다. 따라서 Subsequence가 Substring보다 더 넓은 개념이고, Substring은 Subsequence에 포함된다.

 

왜 DP로 풀어야 하는가?

기본적으로 DP는 중복되는 작업을 줄여서, 시간 복잡도를 개선하는 데에 사용된다. 이 문제를 완전 탐색으로 찾는다면, str1의 모든 부분 수열을 구하고 $O(2^n)$, str2의 모든 부분수열을 구한 다음 $O(2^n)$, 두 부분수열을 비교하여 $O(n)$ 길이의 최댓값을 구해야한다. $O(1)$ 그러면 시간복잡도가 $O(N * 2^n * 2^n)$이 되는데, 생각만 해도 끔찍하다. 다행이도 여기서는 중복되는 작업을 줄일 수 있다. Than과 Then의 부분수열을 찾는다고 해보자. 두 문자열의 LCS는 Thn인데, Th가 길이가 2인 공통부분 수열임을 안다면, Thn이 길이가 3인 공통 부분수열임을 $O(1)$만에 알 수 있다. (여기서 n은 str1과 str2의 길이이다. 물론 길이가 꼭 같으리란 보장은 없지만, 간결함을 위하여)

 

Algorithm Tracing

자, 이제 이 알고리즘을 이해하기 위해서 동작하는 과정을 따라가 보자. 여기서는 Than과 Then을 비교해본다.

Then과 Than을 비교해야 하는데, 우선 Then의 T와 Than의 LCS를 먼저 구한다.

 

	T	h	a	n
T	1
h
e
n

 

T와 T의 LCS의 길이는 1이다.

 

	T	h	a	n
T	1	1
h
e
n

 

T와 Th의 LCS 길이는 1이다.

 

(... 이하 생략 ...)

 

	T	h	a	n
T	1	1	1	1
h
e
n

 

T와 Than의 LCS 길이는 1이다.

 

	T	h	a	n
T	1	1	1	1
h	1
e
n

 

Th와 T의 LCS는 1이다. (T와 T의 LCS와 같다.)

 

	T	h	a	n
T	1	1	1	1
h	1	2
e
n

 

Th와 Th의 LCS는 2이다. (T와 T의 LCS + 1)

 

(.. 이하 생략..)

 

	T	h	a	n
T	1	1	1	1
h	1	2	2	2
e
n

 

(.. 다시 생략 ..)

 

	T	h	a	n
T	1	1	1	1
h	1	2	2	2
e	1	2	2	2
n	1	2	2	3

 

Then과 Than의 LCS의 길이는 3이다!

 

알고리즘 구현 (Java)