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

LCS란?

부분 수열

LCS는 최장 공통 부분 수열로 두 개의 수열이 주어졌을 때, 공통 수열 중 제일 긴 것을 의미한다.

예를 들어서 abcf와 aebwcd가 있다고 생각해 보자.

그렇다면 여기서 나오는 LCS는 abc이다. 

abcf

aebwcd

위의 굵게 표시된 문자들을 보면 알 수 있을 텐데, 공통 부분 수열은 굳이 문자들의 한 번에 이어질 필요가 없다. 공통된 문자가 얼마나 길게 차례대로 나오느냐를 따지는 문제이기 때문이다.

최장 공통 부분 수열

이제 최장 공통 부분 수열을 구하는 방법을 알아보자.

그러기 전에 아래의 유튜브 비디오를 보고 오는 것을 추천한다. 현재 글도 아래 동영상을 기반으로 작성한 것이다.

https://www.youtube.com/watch?v=sSno9rV8Rhg 

LCS의 규칙

LCS를 찾기 위해서는 공통된 문자 수열을 찾아야 한다. 하지만, 위에서 말했듯이 문자들이 굳이 연속될 필요는 없다. 그러나 문자들의 순서가 서로 바뀌어서는 안 된다.

 

예를 들어서 abcdefg와 efgabcd 두 문자의 LCS를 찾는다고 생각해보자.

 

여기서 나오는 공통 부분 수열에는 abcd와 efg가 있다. 그러나 abcdefg 혹은 efgabcd는 공통 부분 수열이 되지 않는다. 왜? 들어가는 문자가 같으니까 공통 부분 수열 아닌가? 이렇게 생각할 수 있지만, 문자의 순서를 지켜야 하니 공통 부분 수열로 인정이 되지 않는 것이다.

 

영상에서도 나왔듯이 두 문자열에서 문자를 이었을 때 선이 교차가 되면 안 되는 것이다.

재귀로 풀기

LCS는 재귀로 푸는 방법과 DP로 푸는 방법 총 두 가지가 있다. 재귀로 푸는 방법은 중복되는 계산이 발생되어 시간과 공간이 낭비될 수 있으므로 DP로 푸는 것이 좋다. 나는 DP로만 LCS를 풀어봤는데, 영상에서 재귀로 푸는 방법을 소개하고 있으니 잠깐 설명하고 DP로 넘어가겠다.

public int LCS(i, j){
	if(i == str1.length() || j == str2.length()){
    	return 0;
    }else if(str1[i] == str2[j]){
    	return 1 + LCS(i+1, j+1);
    }else{
    	return max(LCS(i+1, j), LCS(i,j+1));
    }
}

일단 두 인덱스 중 하나라도 문자열 끝에 가면 종료해야 한다. 문자열을 순서대로 탐색하기 위해 +1을 해줄 텐데, 문자열의 맨 끝에 도착한 경우는 인덱스 에러가 날 수 있기 때문이다.

 

다음으로 문자열 중 문자가 같으면 1을 더해준 값에 두 인덱스를 함께 옮겨준다. 그리고 문자열이 다르면 i만 옮겨준 값과 j만 옮겨준 값에서 더 큰 걸 반환한다.

 

아래는 영상에서 나온 예시로 함수의 생명주기를 풀어쓴 것이다. 영상에서 선생님이 친절하게 설명해주니, 영상을 보며 따라서 써보기를 추천한다.

A, bd'\0'

B, abcd'\0'

 

i가 0이고 j가 0일때, A[0] != B[0] 이므로 LCS(A[1], B[0])와 LCS(A[0], B[1])가 나온다. 

LCS(A[1], B[0])인 경우 A[1] != B[0]이므로 LCS(A[2], B[0])와 LCS(A[1], B[1])가 나온다.

LCS(A[2], B[0])에서 2는 맨 마지막 문자이므로 0을 반환한다.

 

LCS(A[1], B[1])인 경우 A[1] != B[1]이므로 LCS(A[2], B[1])와 LCS(A[1], B[2])가 나온다.

LCS(A[2], B[1])인 경우 A[2]는 맨 마지막 문자이므로 0을 반환한다.

 

LCS(A[1], B[2])인 경우 두 문자가 다르므로 LCS(A[2], B[2])와 LCS(A[1], B[3])이 나온다. 여기서 전자는 맨 마지막 문자를 포함하고 있으므로 0을 반환한다. LCS(A[1], B[3])인 경우 두 문자가 d로 같은 것을 확인할 수 있다! 그러므로 LCS(A[2], B[4])의 반한 값(0이다)에서 1을 더한 값을 반환한다.

 

이게 LCS(A[0], B[0])의 왼쪽 트리이다. 오른쪽 트리 또한 비슷하게 진행함녀 되는데, 재미있는 점은 LCS(A[1], B[2])가 중복되서 나온다는 점이다. 즉, 계산이 중복되므로 이를 DP로 더 빠르게 풀어 쓸 수 있다.

DP

같은 예제이며 다시 한 번 말하지만 동영상을 기반으로 했다.

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

아래 내가 그린 표를 보면서 찬찬히 과정을 이해보자.

이게 초기 표이다.

 

그리고 DP를 위해서 각 행과 열의 0부분을 0으로 채운다.

그리고 (1, 1)부분부터 시작할 것인데, 코드에 나왔듯이 각 문자가 같지 않으므로 (0, 1)과 (1, 0) 중 제일 큰 값을 가지고 온다.

다음에는 (1, 0)과 (0, 2)를 비교해서 (1, 2)에 넣을 차례이다. 이때 두 문자가 같으므로 이번에는 (0, 1)의 값에 1을 더한 값을 현재 위치에 넣어준다.

그리고 다음 (1, 3)의 경우에는 해당하는 두 문자가 같지 않으므로 각 행과 열에 1을 뺀 값들을 비교해 더 큰 값을 넣어준다.

이런 식으로 남은 칸들을 채워주면 아래 표가 된다.

abcd와 bd의 LCS의 길이는 2라는 것을 알 수 있다.

시간 복잡도

이용하는 표에서 알 수 있듯이 n*m이다. 중복되는 계산을 DP로 최소화해 시간 복잡도 문제를 해결한 것을 볼 수 있다.

LCS 문자 찾기

그렇다면 LCS 그 자체를 알고 싶을 때는 어떻게 해야 할까? 어떻게 생각하면 찾을 때보다 간단한 일인데, 역추적으로 돌아가면 된다.

일단 (2, 4)의 입장에서 생각해보자. 내 왼쪽 숫자와 위쪽 숫자인 (2, 3)과 (1, 4)가 같다. 이 말은 즉, (2, 4)는 (1, 3)에서 1을 더한 값이고 이는 (2, 4)에 중복되는 문자가 있다는 의미이다.

 

이렇게 (1, 3)으로 올라가보자. (1, 3)을 기준으로 왼쪽에 있는 값 (1,2)와 오른쪽에 있는 값 (0, 3)은 서로 다른다. 이 말은 즉, 해당하는 두 문자가 서로 다르다는 뜻이며 (1, 3)의 값이 (1, 2)와 (0, 3) 중 더 큰 쪽에서 온 것이라고 할 수 있다. 그러므로 더 큰 값이 (1, 2)로 옮겨간다.

 

이렇게 끝까지 가면 최종 LCS를 찾을 수 있다.

 

아, 문자는 뒤에서부터 찾으니까 스택에 넣어서 관리를 하던지 아니면 reverse()를 사용해줘야 한다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int length1 = str1.length();
        int length2 = str2.length();

        int[][] dp = new int[length1+1][length2+1];

        for(int i=0; i<length1; i++){
            dp[i][0] = 0;
        }

        for(int i=0; i<length2; i++){
            dp[0][i] = 0;
        }

        for(int i=1; i<length1+1; i++){
            for(int j=1; j<length2+1; j++){
                //만일 두 문자가 같으면
                if(str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = 1 + dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        /*
        for(int i=0; i<length1; i++){
            for(int j=0; j<length2; j++){
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }*/

        //맨 뒤에서부터 문자를 확인
        int index1 = length1;
        int index2 = length2;
        while(true){

            if(index1 <= 0 || index2 <= 0){
                break;
            }

            if(dp[index1][index2] == dp[index1-1][index2]){
                index1--;
            }else if(dp[index1][index2] == dp[index1][index2-1]){
                index2--;
            }else{
                sb.append(str1.charAt(index1-1));
                index1--;
                index2--;
            }
        }

        String answer = sb.reverse().toString();
        System.out.println(answer.length());
        if(answer.length() != 0){
            System.out.println(answer);
        }
    }
}

관련 문제

https://www.acmicpc.net/problem/9252

9252번: LCS 2