[백준] 9251번 - LCS

백준 9251번 - LCS

 

 

 

 

LCS - Longest Common Subsequence의 약자로 최장 공통 부분수열을 의미한다. 이전에 풀이한 백준 11053번 가장 긴 증가하는 부분수열(LIS)와는 달리 두 수열이 주어졌을 때, 두 수열의 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 찾아야 한다.

[백준] 11053번 - 가장 긴 증가하는 부분 수열

 

 

 

처음 문제를 접했을 때에 쉽게 풀이법을 떠올리지 못했던 기억이 있다. 결국 다른 사람이 풀이한 풀이를 참고 하였는데 그 당시에는 처음 접하는 풀이법이었기 때문에 이런 접근방법이 있구나 하는 생각과 함께 허탈한 기분이 들었었다.

 

완전 탐색으로 푼다면 주어진 0.1초라는 시간제한 조건에 발목을 잡힐 것이다. 공부하는 입장에서는 해당 문제가 다이나믹 프로그래밍 카테고리에 있다는 것을 인지하고 문제 해결의 실마리를 찾아야 한다.

다이나믹 프로그래밍의 핵심은 전체 문제를 작은 부분으로 나누어서 풀되, 이전에 계산한 결과를 저장하여 동일한 계산을 중복적으로 할 필요가 없게 만드는 것에 있다. 두 문자열의 부분 수열에 대한 최장 공통 부분 수열의 길이를 메모제이션하면서 최종적으로 두 문자열 전체에 대한 최장 공통 부분 수열의 길이를 구한다.

 

 

문제에 주어진 예시로 위 풀이를 적용해보자.

문제에는 ACAYKP(문자열A) 와 CAPCAK(문자열B) 두 문자열이 주어졌다. 

dp[][]		A	C	A	Y	K	P
	(0, 0)	(0, 1)	(0, 2)	(0, 3)	(0, 4)	(0, 5)	(0, 6)
C	(1, 0)	(1, 1)	(1, 2)	(1, 3)	(1, 4)	(1, 5)	(1, 6)
A	(2, 0)	(2, 2)	(2, 2)	(2, 3)	(2, 4)	(2, 5)	(2, 6)
P	(3, 0)	(3, 2)	(3, 2)	(3, 3)	(3, 4)	(3, 5)	(3, 6)
C	(4, 0)	(4, 2)	(4, 2)	(4, 3)	(4, 4)	(4, 5)	(4, 6)
A	(5, 0)	(5, 2)	(5, 2)	(5, 3)	(5, 4)	(5, 5)	(5, 6)
K	(6, 0)	(6, 1)	(6, 2)	(6, 3)	(6, 4)	(6, 5)	(6, 6)

 

 

dp[i][j]은 문자열 A의 j번째 문자까지의 부분수열과 문자열 B의 i번째 문자까지의 부분수열의 최장 공통 부분 수열의 길이가 저장된다.

dp[][]에 값을 넣는 방식은 만약 i행과 j열의 문자가 같으면 i-1 까지의 부분수열과 j-1까지의 부분수열간의 최장 공통 부분수열의 길이 + 1 값을 dp[i][j]에 넣는다. 그러나 i행과 j열의 문자가 같지 않다면 dp[i-1][j] 와 dp[i][j-1] 두 값 중 큰 값이 dp[i][j]에 들어간다. 

 

dp[1][1]에 대한 값은 {A}와 {C} 두 문자열의 최장 공통 부분수열의 길이가 들어간다. 두 문자는 같지 않으므로 0이 들어간다. 마찬가지로 i행 문자(C)와 j열 문자(A)가 같지 않다는 이유에서도 dp[1-1][1-1] = 0이 들어가야 한다.

dp[][]		A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
	0	0	0	0	0	0	0
C(1)	0	0
A(2)	0
P(3)	0
C(4)	0
A(5)	0
K(6)	0

 

다음으로 문자열 A의 부분수열 {A} 와 문자열 B의 부분수열 {C, A}를 비교한다. dp[2][1]에서 2행 문자인 A와 1열 문자인 A는 같으므로 dp[2][1] 은 dp[2-1][1-1] + 1 = 1이 된다. 

dp[][]		A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
	0	0	0	0	0	0	0
C(1)	0	0
A(2)	0	1
P(3)	0
C(4)	0
A(5)	0
K(6)	0

 

다음은 {A}와 {C, A, P} 간의 최장 공통 부분수열의 길이인 dp[3][1]에 대한 값을 찾는다. 3행 문자인 P와 1열 문자인 A는 같지 않으므로 dp[3-1][1] = 1과 dp[3][1-1] = 0 두 값 중 더 큰 값인 1이 dp[3][1]에 들어간다. 

dp[][]		A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
	0	0	0	0	0	0	0
C(1)	0	0
A(2)	0	1
P(3)	0	1
C(4)	0
A(5)	0
K(6)	0

 

 

중간 과정에 대해서도 살펴보자면

dp[][]		A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
	0	0	0	0	0	0	0
C(1)	0	0	1	1	1	1
A(2)	0	1	1	2	2	2
P(3)	0	1	1	2	2	2
C(4)	0	1	2	2	2	2
A(5)	0	1	2	3	3
K(6)	0	1	2	3	3

표가 위와 같이 채워졌을 때 다음에 올 dp[5][5]에는 어떤 값이 들어갈까? A와 K는 같지 않기 때문에 K를 추가하기 이전의 부분 수열까지의 최장 공통수열의 길이와 A를 추가하기 이전의 부분 수열까지의 최장 공통수열의 길이 중 더 큰 값인 3이 들어간다.

dp[][]		A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
	0	0	0	0	0	0	0
C(1)	0	0	1	1	1	1
A(2)	0	1	1	2	2	2
P(3)	0	1	1	2	2	2
C(4)	0	1	2	2	2	2
A(5)	0	1	2	3	3	3
K(6)	0	1	2	3	3

 

반면 dp[6][5]에는 두 문자가 K로 같으므로 두 부분 수열에 K가 추가되기 이전인 dp[6-1][5-1]에 1이 더해진 값이 dp[6][5]에 들어간다.

dp[][]		A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
	0	0	0	0	0	0	0
C(1)	0	0	1	1	1	1
A(2)	0	1	1	2	2	2
P(3)	0	1	1	2	2	2
C(4)	0	1	2	2	2	2
A(5)	0	1	2	3	3	3
K(6)	0	1	2	3	3	4

 

 

 

이런 방식으로 위 표를 전부 채우게 되면 아래와 같이 된다.

dp[][]		A(1)	C(2)	A(3)	Y(4)	K(5)	P(6)
	0	0	0	0	0	0	0
C(1)	0	0	1	1	1	1	1
A(2)	0	1	1	2	2	2	2
P(3)	0	1	1	2	2	2	3
C(4)	0	1	2	2	2	2	3
A(5)	0	1	2	3	3	3	3
K(6)	0	1	2	3	3	4	4

 

 

 

 

전체 코드

 

TopDown 방식

import java.util.*;

public class Main {
    
    static char[] A;
    static char[] B;
    static Integer[][] dp;
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        A = sc.nextLine().toCharArray();
        B = sc.nextLine().toCharArray();
        
        dp = new Integer[B.length+1][A.length+1];
        
        for (int i=0; i<A.length+1; i++) dp[0][i] = 0;
        for (int i=0; i<B.length+1; i++) dp[i][0] = 0;
        
        System.out.println(LCS(A.length, B.length));
                           
        sc.close();
    }
    
    static int LCS (int X, int Y) {
    	
    	int x = X-1;
    	int y = Y-1;
        
        if (dp[Y][X] == null) {
            
            if (A[x] == B[y]) dp[Y][X] = LCS(X-1,Y-1)+1;
            
            else dp[Y][X] = Math.max(LCS(X-1, Y), LCS(X, Y-1));
        }
        
        return dp[Y][X];
    }
}

 

BottomUp 방식

import java.io.*;

public class Main {
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        
        int[][] dp = new int[str1.length+1][str2.length+1];
        
        
        for (int i=0; i<str1.length; i++) {
            for (int j=0; j<str2.length; j++) {
                
                if (str1[i] == str2[j]) dp[i+1][j+1] = dp[i][j] + 1;
                else dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
                
            }
        } 
        
        System.out.println(dp[str1.length][str2.length]);
       
        br.close();
    }
}