동적계획법 (Dynamic Programming) - (3) 최장 공통 부분수열(LCS)

신찬수 교수님의 
알고리즘 동적계획법 - LCS 문제 영상을 정리했습니다.

 

동적계획법의 순서 다시 정리 !

 

1. 해를 분석 후 부문제로 분할
2. 부문제의 해로 큰 문제의 해를 표현(점화식)
3. 적당한 순서로 DP table을 채우기
4. DP table에서 원문제의 해를 계산하고 알고리즘의 정당성 증명

 

LCS(Longest Common Subsequence) 문제

주어진 수열에서 일부 원소(문자)를 지웠을 때 남은 수열(문자열)을 부분 수열이라고 한다.

주의할 것은 원래 수열에서 연속하지 않아도 된다는 것이다.

 

영어 대문자로 구성된 X, Y 문자열이 주어진다. 

X = ABCDDAB

Y = BDCABA

 

이때 ABCDDAB에서 부분 수열이라고 하면 ABCDDAB의 CDD와 같이 연속으로 이어진 것만 가능하다고 생각하기 쉬운데, 실제로는 ABCDDAB와 같이 BDDB도 부분 수열이 된다.

(나 홀로 생각..)
대충 문자열에서 n개의 문자를 뽑아서 원래 문자열에 존재하는 순서대로 나열한 것이 부분 수열인 거 같다!
(이때 n은 1에서부터 문자열의 길이가 된다.)

공통 부분 수열이라는 것은 X,Y 동시에 들어있는 부분 수열을 의미한다.

 

예를 들면 BCAB가 있다.

X = ABCDDAB

Y = BDCABA

 

최장 공통 부분 수열(LCS) 문제는 가장 긴 길이의 공통 부분 수열을 찾는 문제이다.

 

@X_{n} = x_{1}x_{2}...x{n}@

@Y_{m} = y_{1}y_{2}...y{m}@

 

@X_{3} = x_{1}x_{2}x_{3}@가 되고@Y_{2} =y_{1}y_{2}@가 된다.

 

LCS(@X_{n}@,@Y_{m}@) = @X_{n}@, @Y_{m}@의 최장길이 공통 부분 수열의 길이

LCS(i,j) = @X_{i}@와 @Y_{j}@의 LCS의 길이

@x_{i}@와 @y_{j}@가 서로 같은 경우와 다른 경우 두 가지 경우가 존재한다.

 

만약 @x_{i}@ == @y_{j}@ 라면 이 문자를 최장 길이 공통 부분 수열 마지막에 집어 넣는다.

이 때 구해진 최장 길이 공통 부분 수열은 @x_{1}x_{2}...x_{i-1}@와 @y_{1}y_{2}...y_{j-1}@에서 구해진 최장 길이 공통 부분 수열이 된다.

 

만약 @x_{i}@ != @y_{j}@ 면 둘 중에 하나가 최장 길이 공통 부분 수열의 마지막에 들어갈 수 있고, 둘 다 안 들어갈 수도 있다. 주의할 점은 둘다 들어가는 경우는 존재하지 않는다는 것이다. 

만약 @x_{i}@가 안뽑히는 경우는 LCS(i-1, j)를, @y_{j}@가 안뽑히는 경우는 LCS(i, j-1)을 구하면 된다. 

LCS(i,j-1)과 LCS(i-1,j) 중 최댓값이 답이 된다. 

 

LCS(i,j) = LCS(i-1, j-1) + 1 if @x_{i}@ == @y_{j}@ 
LCS(i,j) = max(LCS(i-1,j), LCS(i,j-1)) if @x_{i}@ != @y_{j}@ 

 

LCS(i,j)를 풀기위해선 LCS(i-1, j-1)과 LCS(i-1,j), LCS(i,j-1)이 계산되어있어야 한다.

-> LCS[i][j] 라는 2차원 배열을 생성하여 값을 저장한다. 

LCS[i][j] = LCS[i-1][j-1] +1 OR max(LCS[i-1][j], LCS[i][j-1])

 

X\Y	0	B	D	C	A	B	A
0
A
B
C
B
D
A
B

 

이때 LCS[7,6] = LCS(@X_{7}@, @Y_{6}@)이고 우리가 구해야 할 최종 답이다!

 

LCS(0,j) = 0, LCS(i,0) = 0으로 초기화를 해준다. (빈문자열과 공통 문자열은 존재하지 않기 때문이다). 

 

X\Y	0	B	D	C	A	B	A
0	0	0	0	0	0	0	0
A	0
B	0
C	0
B	0
D	0
A	0
B	0

 

이 때 LCS[i][j]를 구하려면 같은 경우에는 LCS[i-1][j-1]이, 같지 않은 경우에는 LCS[i-1][j], LCS[i][j-1]을 알아야 한다.

 

LCS[i-1][j-1]	LCS[i-1][j]
LCS[i][j-1]	LCS[i][j]

 

LCS[i][j]를 구하기 위해선 세 개의 값을 다 알아야한다. 따라서 왼쪽위에서 오른쪽 아래로 가는 방향으로 행을 채워야한다.

즉 앞의 행부터 차례대로 채워주면 된다. 

 

위의 공식을 적용하여 순서대로 값을 채우면 아래와 같은 배열이 완성된다.

 

X\Y	0	B	D	C	A	B	A
0	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

 

채워야 할 칸은 NxM칸이고, 각 칸을 채우는데 걸리는 시간은 O(1)이다.

따라서 걸리는 총 시간은 O(NM)이 된다. 

 

이때 LCS의 길이가 아닌 실제 LCS가 뭔지 구하고 싶은 경우, 역추적해서 구하면 된다.

LCS[7][6]에서 부터 시작해서 이동하면 된다.

 

X\Y	0	B	D	C	A	B	A
0	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

 

대각선으로 이동할 때마다 직전의 문자를 저장한다.

A -> B -> C -> B 가 되고, 이를 역순으로 배치하면 구하는 최장 공통 부분 수열인 BCBA가 된다. 

 

직접 구현한 코드 (JAVA)

(백준 9251번 LCS)

http://boj.kr/73e490117d79462b9fade6782e829d27

공유 소스 보기

 

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));
        String X = br.readLine();
        String Y = br.readLine();
        int [][] LCS = new int[X.length()+1][Y.length()+1];
        for (int i = 0; i <= X.length(); i++) {
            LCS[i][0] = 0;
        }
        for (int i = 0; i <= Y.length(); i++) {
            LCS[0][i] = 0;
        }
        for (int i = 1; i <= X.length(); i++) {
            for (int j = 1; j <= Y.length(); j++) {
                if (X.charAt(i-1) == Y.charAt(j-1)){
                    LCS[i][j] = LCS[i-1][j-1] +1;
                } else {
                    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
                }
            }
        }
        System.out.println(LCS[X.length()][Y.length()]);
    }
}

 

(참고) charAt 할때 인덱스를 주의해야한다!

 

직접 구현한 코드 (JAVA) 

(백준 9252번 LCS2)

http://boj.kr/e564598995e54d30a8c8b0c2e185349f

공유 소스 보기

 

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));
        String X = br.readLine();
        String Y = br.readLine();
        int [][] LCS = new int[X.length()+1][Y.length()+1];
        for (int i = 0; i <= X.length(); i++) {
            LCS[i][0] = 0;
        }
        for (int i = 0; i <= Y.length(); i++) {
            LCS[0][i] = 0;
        }
        for (int i = 1; i <= X.length(); i++) {
            for (int j = 1; j <= Y.length(); j++) {
                if (X.charAt(i-1) == Y.charAt(j-1)){
                    LCS[i][j] = LCS[i-1][j-1] +1;
                } else {
                    LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
                }
            }
        }
        int i = X.length();
        int j = Y.length();
        StringBuilder sb = new StringBuilder();
        while (i > 0 && j > 0) {
            if (X.charAt(i-1) == Y.charAt(j-1)){
                sb.append(X.charAt(i - 1));
                i--; j--;
            } else {
                if (LCS[i][j] == LCS[i - 1][j]){
                    i--;
                } else {
                    j--;
                }
            }
        }
        sb.reverse();
        System.out.println(LCS[X.length()][Y.length()]);
        System.out.println(sb);
    }
}