https://www.acmicpc.net/problem/9251
https://www.youtube.com/watch?v=EAXDUxVYquY
유튜브 강의의 내용을 내 나름대로 정리해 보았다.
아래 예제를 갖고 문제를 보자.
example
X5 = "abcdef"
Y5 = "dbdkcf"
// 여기서 LCS (최장 공통 부분 수열) 는 bdf 이다.
첫 번째로 비교 하는 두 문자가 같은 경우이다.
이런 경우 f는 두 문자열이 공통으로 가진 문자이므로 전체 LCS 에 당연히 포함 될 것이다. X5와 Y5는 공통 문자열에 포함하는 되는 것을 알았으니 그 이전 LCS에 대해 1을 해준 값이 현재 LCS의 길이가 된다.
즉, X5 와 Y5의 LCS 길이는 각 문자열 사이의 이전 LCS (=LCS(4,4) + 1) 인 셈이다.
이제 LCS (4,4)를 보자.
비교하는 문자가 서로 다를 경우이다. 이 경우에는 위에 나와있듯이 세 가지 경우가 있다.
X4, X5 둘 중 한 문자가 LCS에 포함된다면 나머지 한 문자는 LCS에 포함되지 않는다. 둘 다 포함된다면 같은 문자여야 할 것이기 때문이다.
하지만 현재 X4와 Y4를 비교하는 시점에서는 X4가 LCS에 포함되어있는지, Y4가 LCS에 포함되어 있는지, 아니면 둘 다 포함이 되어있지 않는지 알 수 없다. (dp문제가 다 그렇지 뭐)
그러니 논리적으로 X4가 LCS에 포함된 경우와, Y4가 LCS에 포함 된 경우 둘 중 더 큰 경우를 LCS로 하자는 거다. 이 경우 앞서 말했듯 X4가 포함 된 경우 X4와 Y3을 비교해야 하는데 그 이유는 둘 중 한 문자가 포함되었다면 나머지 문자는 포함되지 않기 때문에 Y4에 이전 문자인 Y3과 비교해 주는 것이다. 이 과정을 재귀적으로 반복하다 보면 X4 와 Y3비교 (다름) X4 와 Y2 비교 (다름) X4 와 Y1 비교 (다름) X4와 Y0 비교 (다름) return 문자가 서로 다를 경우 이런 식으로 계속 비교가 가능하다.
LCS(4,4) = max(LCS(4,3) , LCS(3,4))
그러면 점화식이 도출되었다
// i,j는 두 문자열의 길이이다. 길이가 서로 다른 경우도 존재하므로 변수 두개 사용.
if(X[i] == Y[j]) { // 같을 경우
LCS(i,j) = LCS(i-1,j-1) + 1
} else { // 다를 경우
LCS(i,j) = max(LCS(i-1,j), LCS(i,j-1))
}