DP 알고리즘 | LCS (최장 길이 공통 부분 수열)

LCS (Longest Common Subsequence)

• 두 개의 문자열 X, Y가 주어졌을 때, X와 Y에서 공통으로 나타나는 부분 문자열을 찾고자 한다.
• 부분 문자열 길이가 최대가 되도록 부분 문자열 찾는 방법은 ?  

---

LCS 는 두 개의 문자열 X, Y가 주어졌을 때 공통의 부분 문자열 길이 최대값을 찾는 문제다. 

X = ABDCDC
Y = ACADC 
=>  두 문자열 최장 길이 공통 부분 수열은 길이 4의 "ACDC " 가 된다.  

DP[i][j] 의 정의 :  각 위치 인덱스를 각각 마지막 문자로 포함하는 두 문자열의 LCS 길이값  
즉, A[i]와 B[j] 를 기준으로 경우를 나눠 D[i][j]에 최장 길이를 갱신해줘야 한다.

=>  D[i][j]에 올 수 있는 값의 경우는 크게 4가지로 나눌 수 있다. 
 (2X2) : A[i]가 포함O / X,   B[j] 포함 O / X

(1) A[i] 가 LCS에 포함되지 않는 경우 -> D[i][j] = D[i-1][j] 로 둔다.
(2) B[j] 가 LCS에 포함되지 않는 경우 -> D[i][j] = D[i][j-1] 로 둔다.
(3) A[i]와 B[j] 모두 포함되지 않는 경우(i=0. j=0) -> D[i][j] = 0
(4) A[i]=B[j] 여서 LCS에 포함되는 경우  -> D[i][j] = D[i-1][j-1] + 1                                            
                                                       //즉, A,B 둘다 포함 전의 D[i-1][j-1] 값에 + 1 처리 하겠다는뜻

설명 1

---

예를 들어, 전체 DP[][] 배열에서 일부 사각형만 빼놓고 아래 그림처럼 봐보자.

현재 DP[A][C]의 위치에 올 수 있는 값을 세팅하려면 이전 DP[][] 값을 참고하기는 해야 하는데,
우리는 어쨋든 현재 칸에도 최대 중복 수열의 길이 LCS 길이를 쓰고 싶다.
 
DP[A][C]의 값에 담을 값을 고려할 때는
DP[A][D] : (왼쪽칸) 의 값과 DP[C][C] : (위쪽 값) 중에서 더 큰 값으로 세팅해야 한다.

A는 포함하지만 C는 안포함하는 왼쪽 칸 D[A][D] 의 LCS 길이와
A는 안포함하지만 C는 포함하고 있는 위쪽 칸 D[C][C] 의 LCS 길이 중
더 큰 길이를 활용해서 현재의 LCS 를 세팅해야
추후에도 계속해서 더 큰 LCS 길이로 값을 세팅할 수 있기 때문이다.

설명2