LCS (Longest Common Subsequence, 최장 공통 부분 수열)

LCS(Longest Common Subsequence, 최장 공통 부분 수열)

---

 

LCS (Longest Common Subsequence)

• 최장 공통 부분 수열
• 두 문자열이 주어졌을 때, 두 문자열 모두에 순서를 유지하며 등장하는 가장 긴 부분 수열ex ) ACAYKP와 CAPCAK의 LCS는 길이가 4인 ACAK

만약 brute force로 길이가 N인 문자열에 대해서 부분 수열을 구한다면? - > 2^N의 시간복잡도
이를 다시 길이가 M인 문자열에 대해 확인해본다면 대략 O(2^N × M) .. 시간 초과

DP (동적 계획법, Dynamic Programming) 

• LCS는 문자열 각 문자의 위치에 대한 연산이 반복됨
• DP는 작은 문제의 답을 저장해두고, 이를 이용해 큰 문제의 답을 빠르게 구하는 방식
• ACAYKP에 대해 C->A->P->C->A->K의 위치에 대한 연산의 답을 저장하고, 위치의 누적합을 구하는 방식
• "순서"에 주목하여 dp배열을 채워나가보자

dp[i][j] = A의 앞 i글자, B의 앞 j글자에서의 LCS 길이

dp[][]	A	C	A	Y	K	P
C	0	0+1=1	...
A	1	1		...
P	1	1			...
C	1	1+1=2				3
A	1	2				3
K	1	2				4

 

A와 CA에서 부분수열이 갱신되므로 1

A와 CAPCA에서 A가 다시 만나도 이미 앞에서 A를 만났기에 부분수열은 1로 유지

AC와 CAPC를 본다면 이전 A와 CAPC에서까지 만났을때 dp배열은 1로 저장되었기에 그에 1이 증가한 값을 저장한다.

...위 과정을 반복해서 채워나간다면

dp[len][len]에 LCS길이를 구할 수 있다.

---

관련 문제

백준 LCS 문제

https://www.acmicpc.net/problem/9251 LCS ( LCS 길이만 구하는 문제 )

https://www.acmicpc.net/problem/9252 LCS2 ( LCS 길이, 수열 자체까지 구하는 문제 )

 

---

 

1. LCS 길이 구하기 ( 백준 9251 ) 

• 입력 : 알파벳 대문자로 이루어진 2개의 문자열 , 출력 : LCS의 길이
• 시간 제한 : Java 기준 0.4 초 ( brute force는 시간 초과)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String A = br.readLine();
        String B = br.readLine();

        int n = A.length();
        int m = B.length();

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[n][m]);  // LCS 길이 출력
    }
}

 

• dp[i][j] = A의 앞 i글자, B의 앞 j글자에서의 LCS 길이

if (A.charAt(i - 1) == B.charAt(j - 1)) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}

• A의 i-1번째 문자와 B의 j-1번째 문자가 같다면,
  → 이 문자를 LCS에 포함시킬 수 있음
• 따라서 직전 상태인 dp[i-1][j-1]에 +1 하면 됨
  → +1은 이번 문자를 새로 포함했다는 뜻 

--> 이는 AC와 CAPC를 본다면 이전 A와 CAPC에서까지 만났을때 dp배열은 1로 저장되었기에 그에 1이 증가한 값을 저장한다.
을 코드로 구현 한것

 

 

• 문자가 다르면 이번 글자는 공통이 아니므로 버림
• 그럼 LCS는 A의 i-1까지 보거나, B의 j-1까지 보거나 긴것으로 가져간다.

 

---

2. LCS 길이 구하기 + LCS 구하기 ( 백준 9252 ) 

• 입력 : 알파벳 대문자로 이루어진 2개의 문자열 , 출력 : LCS의 길이, LCS 문자열
• 시간 제한 : Java 기준 0.4 초 ( brute force는 시간 초과)

이번에는 LCS 자체를  구해야한다.
앞서 dp를 통해 배열의 길이는 구했다. 이를 이용해서 dp 테이블을 역추적(backtracking) 해서 공통 수열을 재구성 할 수 있다.

dp[][]	A	C	A	Y	K	P
C	0	0+1=1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	1+1=2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

 

다시 ex ) ACAYKP와 CAPCAK의 LCS는 길이가 4인 ACAK를 표시해본다면 다음과 같다.
우측 하단 K,P 부터 시작해서
일치하면 부분순열의 문자에 추가, 일치하지 않는다면 좌측,상단 중 높은 값으로 이동...을 C,A 까지 반복해보자.
dp 배열 자체가 LCS값이 높다는 것은 LCS에 해당하는 문자 케이스여서 정수가 +1 된 것임을 의미하기에 높은 값을 따라가며
추가하면 BackTracking 방식으로 다시 LCS를 구할 수 있다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String A = br.readLine();
        String B = br.readLine();

        int n = A.length();
        int m = B.length();

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

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        StringBuilder lcs = new StringBuilder();
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                lcs.append(A.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        lcs.reverse();  
        System.out.println(dp[n][m]);     
        if(dp[n][m]!=0)
            System.out.println(lcs.toString());  
    }
}

 

문자열의 뒤부터 시작해서 같은 문자면 lcs stringBuilder 객체에 추가하고
일치하지 않으면 dp높은 방향성으로 문자열을 0이 될때까지 인덱스를 조절한다.