[알고리즘] LCS (최장 공통 부분 수열)

목차

LCS란?

LCS는 Longest Common Subsequence의 약자이다. 말 그대로 가장 긴 공통된 부분 수열이다. LCS는 보통 주어진 두 수열에서 각각의 부분 수열들 중, 서로 같은 부분 수열 중에서 가장 긴 부분 수열을 뜻한다. LCS는 DP(다이나믹 프로그래밍)의 대표 유형 중 하나고 백준에서는 최소 난이도가 골드5 정도 된다. 따라서 LCS를 알면 DP 골드 문제들을 조금씩 풀 수 있게 된다.

 

예시를 하나 보겠다.

s1 = ACAYKP, 그리고 s2 = CAPACK라고 하겠다.

 

문제 예시로 보자면

ACAYKP의 부분 수열을 표현하면 다음과 같다.

ACAYKP : {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, ⋯ , {A, C, A, Y, K, P} 

 

CAPCAK의 부분 수열을 표현하면 다음과 같다.

CAPCAK :{C}, {A}, {P}, {C}, {A}, {K}, {C, A}, ⋯ , {C, A, P, C, A, K} 

 

각각의 부분 수열 중 서로 같은 부분 수열들도 있고 공통이 아닌 부분 수열도 있을 것이다.

예로 들면 {A}, {C}, {K}, {P}, {C, A}, {A, C, A}, {A, C, A, K} 등등이 있다. LCS는 이 부분 수열들 중에서 가장 공통부분이 큰 부분 수열을 구하는 알고리즘이다. 

ACAYKP

CAPCAK

이 예시에서는 {A, C, A, K}이다.

 

 

LCS 접근 방법 & 예시

LCS를 접근할 때 보통 문자열 두 개가 주어진다. 이를 s1과 s2라고 하겠다. 그리고 s1 문자열의 길이를 n, s2 문자열의 길이를 m이라고 하겠다. 이렇게 주어지면 2차원 배열을 만들고 맨 앞 문자부터 차례대로 비교하여 부분 수열의 길이를 누적해보는 방식이다.

int[][] dp = new int[n][m];

dp [i][j] = 첫 번째 문자열의 i번째, 두 번째 문자열의 j번째까지 봤을 때 가장 긴 공통부분 문자열을 표현하는 2차원 배열이다.

if (arr[i] == arr[j]) dp[i][j] = dp[i-1][j-1] + 1;
 
if (arr[i] != arr[j]) dp[i][j] = max(dp[i][j-1], dp[i-1][j]);

 

 

예시를 하나 들면서 배열을 채워보겠다.

s1 = CAPCAK, 그리고 s2 = ACAYKP라고 하겠다. 그러면 n과 m은 문자열들의 길이 이므로 n = 6 그리고 m = 6이 된다.

배열을 만들면 다음과 같다.

 

s1의 첫 번째 문자인 'C'는 {A, C, A, Y, K, P}에 있으므로 1로 표시한다.

{C}와 {CAY} 나 {CAYKP}의 최장 공통부분 수열은 똑같이 {C} 이므로 나머지도 C 이후도 똑같이 1로 표시해준다. 

그다음 문자인 A도 하면 다음과 같이 나온다.

이렇게 계속하면 다음과 같이 나온다.

따라서 가장 긴 공통된 부분 수열은 배열 맨 아래 오른쪽에 있는 수 (dp [n][m])이다.

 

 

백트래킹

단순히 두 문자열의 LCS의 길이를 구하는 게 아니라 LCS를 구하고 싶으면 백트래킹 (역추적)을 해야 한다. 백트래킹은 반대로 하면 된다. 

일단 시작은 dp [n][m]에서 한다.

 

만약에 arr [i] == arr [j]이고 dp [i][j] = max면 dp [i-1][j-1]로 이동한다. 그리고 max = max -1 해준다.

만약에 dp [i-1][j] = dp [i][j] 면 dp [i-1][j]로 이동하고 dp [i][j-1] == dp [i][j] 면 dp [i][j-1]로 이동한다.

따라서 CAPCAK와 ACAYKP의 LCS는 ACAK이고 LCS의 길이는 4인 것을 확인할 수 있다.