백준 9251) LCS

www.acmicpc.net/problem/9251

9251번: LCS

 

문제

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

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

입력

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

출력

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

 

 

---

 

LCS 문제는 주어진 문자열들을 비교해서 공통적으로 증가하는 부분 수열 중에서 가장 긴 것을 찾는다.

 

문제에서 제시한 예제를 보며 이해를 돕자면,

 

예제 입력

ACAYKP

CAPCAK

 

예제 출력

4

 

 

ACAYKP - CAPCAK

 

각각의 문자열들의 공통적인 부분 수열을 체크하는 방식으로써 ACAK가 가장 긴 것이라고 볼 수 있다.

처음에 이 문제를 풀려고 했을 때, '공통 부분 수열'이라는 말에 공통이라면 당연히 CA가 아닌가? 라는 생각이 들었다.

 

하지만 문제를 곱씹어보면서

 

1) 가장 긴 것 을 찾는 점

2) 예시로 LCS가 ACAK 라고 주어진 점

 

-> CA와 같이 끊어짐이 없는 수열을 말하는 게 아니라 끊어져 있어도 부분 수열이기 때문에 가능하다고 생각했다.

 

 

 

그렇다면 어떻게 문제를 접근해야 될까?

 

예시를 빌려서 'ACAYKP'라는 문자열과 'CAPCAK'라는 문자열이 있을 때

문자 하나하나씩 서로 비교 (최대한 잘게 쪼갠다.) 하되,

순차적으로 문자열을 늘리면서 (쪼갠 것을 조합한다.)

최댓값 (최적의 해)를 찾는 것이므로 다이나믹 프로그래밍으로 접근한다.

 

 

 

잘 알려져 있는 점화식은 다음과 같다.

X : String, Y: String , dp[i][j] 에 대해서

if X[i] == Y[j] -> dp[i-1][j-1] + 1
if X[i] == Y[j] -> max(dp[i-1][j], dp[i][j-1])

 

점화식이 이해가 되지 않더라도, 막상 표를 그리면서 하나하나씩 따라가다보면 이해가 충분히 된다.

 

 

 

1) 길이가 0일 때는 비교할 것이 없으므로 0을 대입한다.

 

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

 

2) row==C 일 때 col== A..P 까지 각각 비교한다.

만약 같다면 대각선 왼쪽 방향의 값 + 1 을 해준다.

같지 않다면 위와 왼쪽 중에서 가장 큰 값을 대입한다.

 

	0	A	C	A	Y	K	P
0	0                  0 (+1)                   |  0         ㅡ      0		0	0	0	0	0
C			1	1	1	1	1
A	0
P	0
C	0
A	0
K	0

 

3) 위의 패턴을 반복한다.

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

 

각 문자마다 같을 때 대각선 왼쪽을 더해주는 이유는

이전까지의 결과값에서 새로운 공통 문자를 찾았으므로 1을 더해주는 것이다.

 

그리고 같지 않을 때 왼쪽과 위쪽을 비교해서 최댓값을 입력하는 이유는

둘 중에서 큰 값으로 입력하게 되면 공통 부분 수열을 이루기 때문이다.

 

 

 

다음은 전체 코드이다.

 

import java.io.*
import kotlin.math.max

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val str1 = br.readLine()
    val str2 = br.readLine()
    val dp = Array(str1.length+1) {IntArray(str2.length+1)}

    for(i in 1 until str1.length+1) {
        for(j in 1 until str2.length+1) {
            if(str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    println(dp[str1.length][str2.length]) 
}