다이나믹 프로그래밍 (최장 공통 부분 수열 LCS)

ACAYKP

CAPCAK

앞의 문자열의 sub sequence를 X, 뒤의 문자열의 sub sequence를 Y라고 했을 때 문자를 하나씩 늘려가면서 비교해보자

X: A

Y: C

두 문자열로 만들 수 있는 LCS의 길이는 0이다.

 

X: A

Y: CA

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

 

X: A

Y: CAP

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

 

X: A

Y: CAPC

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

위와 같이 Y가 끝까지 CAPCAK까지 구하게 된다면 X를 하나씩 늘려주면 된다.

 

X: AC

Y: C

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

 

X: AC

Y: CA

두 문자열로 만들 수 있는 LCS의 길이는 1이다.

 

표를 만들고 채우기 위해 값이 증가하는 방식을 살펴보면 다음과 같이 정의할 수 있다.

 

X와 Y에 가장 최근에 추가된 글자가 서로 같을 때

dp[i][j] = dp[i - 1][j - 1] + 1                          // 길이는 (두 글자가 추가되기 전 가장 큰 길이 + 1)이 됨

추가된 글자가 서로 다를 때

dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])          // 기존에 주어진 문자열로 만들 수 있던 최대 길이를 갖게 됨

출처: https://suri78.tistory.com/11 [공부노트]

LCS는 변형해서 많이 나오는 문제이기 때문에 근본을 완벽히 이해해 놓으면 잘 활용해 문제를 풀 가능성이 높다.