[백준] no9251: LCS - DP문제

문제

LCS : 최장 공통 부분 수열

두 개의 문자열이 주어진다.

각 문자열에서 순차적으로 뽑을 수 있는 문자열 중, 공통되는 부분 문자열의 최대 길이를 출력해라.

이때, 각 문자열의 최대 길이는 1000자.

문제 링크 : https://www.acmicpc.net/problem/9251

예시 1
ACAYKP와 CAPCAK의 LCS는 ACAK

예시 2
DCBAB와 CABCD의 LCS는 CAB

---

원리

첫 번째 수열의 부분수열과 두 번째 수열의 부분수열을 추출해서 => 각 부분수열의 부분수열을 비교한다.

1. 각 부분 수열별 최대 LCS표

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	1	2	2	2
P	1	1	1	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

 

2. 각 부분수열의 공통부분수열 비교 설명 

 

3. 위의 원리를 바탕으로 알고리즘을 적용하면 된다.

 

---

풀이방법

핵심 재귀 코드 :

1. 이차원 배열의 가장 첫번째칸부터 순차적으로 재귀 반환이 이루어지며

2. 만약 부분수열에 적용될 두 문자가 같으면 +1, 다르면 이전까지 중 가장 많이 겹친 수열의 길이를 재귀반환

3. 최종적으로 가장 맨 끝 칸에는 제일 긴 부분 수열의 길이가 되므로 이 값을 최종 반환

    private static String first, second;
    private static Integer[][] DP; // null값으로 체크하기 위해 int가 아닌 Integer사용

    ...

    /**
     * 
     * @param y : DP[][]의 Y축
     * @param x : DP[][]의 X축
     * @return
     */
    private static int recur (int y, int x) {

        // 만약 음수가 되는 경우(2차원 배열의 범위를 벗어나는 경우) => 누계를 위해 0을 리턴
        if(y<0 || x<0) return 0;
        
        if(DP[y][x]==null) { // 해당 칸에 처음 방문하는 경우
            DP[y][x] = 0; // 우선 0으로 초기화
            if(first.charAt(y) == second.charAt(x)) { // 만약 현재 선택한 두 수열에서의 문자가 같은 경우
                DP[y][x] = recur(y-1, x-1) + 1; // 직전에 구한 최대치에 +1 해라
            }
            else { // 비교하는 두 문자가 다른 경우
                DP[y][x] = recur(y-1, x) >= recur(y, x-1) ? recur(y-1, x) : recur(y, x-1); // 더 최대값인 경우를 입력
            }
        }
        return DP[y][x]; // 최종적으로 구해진 최대값은 이차원 배열 DP의 맨 마지막자리에 입력된 수
    }

---

나의 코드

시도 1. 이중 반복을 이용한 비교방식 - [실패]

원인 : 첫 번째 문자열에 대한 순차적인 비교만 이루어져 LCS를 못찾음

반례 : 

DCBAB
CABCD

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    /*
     * 1. first를 순차적으로 순회
     * 2. 만약 first의 현재(i번째) 문자가 second의 현재(j)번째와 일치할 경우 cnt+1 해주고
     * 3. i+1문자부터 이어서 순회하며 j+1문자부터 비교 순회
     * 4. 만약 i번쨰 문자가 j의 끝까지 순회하는 동안 일치하는 문자가 없었다면 i+1번째 문자로 다시 j번째부터 순회
     */

    public static void main(String[] args) throws IOException {
        String first = br.readLine();
        String second = br.readLine();
        int cnt = 0; // LCS의 최장길이
        int check1 = 0; // 첫 번째 문자열의 현위치
        int check2 = 0; // 두 번째 문자열의 현위치
        int last = 0; // 두 번째 문자열에서 마지막으로 공통부분이 있었던 위치의 다음위치

        while(true) {
            if(check1==first.length()) break; // 첫 번째 문자열의 끝까지 모두 확인한 경우 종료
            char now1 = first.charAt(check1); // 첫 번째 문자열에서의 현재 문자 => 이 문자와 두 번째 문자열의 문자를 비교할 예정
            
            // 두 번째 문자열 순회 (이떼, 두 번째 문자열중 마지막으로 일치했던 문자 다음부터 순회)
            while(true) {
                if(check2==second.length()) break; // 두 번째 문자열의 끝까지 모두 확인한 경우 종료
                char now2 = second.charAt(check2); // 두 번째 문자열에서의 현재 문자

                if(now1==now2) { // 일치하는 문자열이 있는 경우
                    cnt++;  // LCS의 길이 + 1
                    last = check2 + 1; // 마지막으로 일치했던 두 번째 문자열에서의 문자 위치 다음 위치를 기록
                    break;
                } 
                
                // 두 번째 문자열의 현재 문자가 일치하지 않는 경우, 두 번째 문자열의 다음 문자로 이동  
                check2++;
            }  
            
            // 첫 번째 문자열에서의 현재 문자와, 두 번째 문자열의 비교가 끝난 경우
            check2 = last; // 첫 번째 문자열에서의 다음 문자는, 두번째 문자열에서의 마지막으로 일치했던 문자 다음부터 비교할 것임
            check1++; // 첫 번째 문자열에서의 다음문자로 넘어감
        }

        System.out.println(cnt);
    }

 

시도 2. DP를 이용한 방식으로, 위에 설명한 원리가 적용된 방법 [성공]

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static String first, second;
    private static Integer[][] DP; // null값으로 체크하기 위해 int가 아닌 Integer사용

    public static void main(String[] args) throws IOException {
        first = br.readLine();
        second = br.readLine();
        
        DP = new Integer[first.length()][second.length()];

        int LCS = recur(first.length()-1, second.length()-1);

        System.out.println(LCS);
    }    

    /**
     * 
     * @param y : DP[][]의 Y축
     * @param x : DP[][]의 X축
     * @return
     */
    private static int recur (int y, int x) {

        // 만약 음수가 되는 경우(2차원 배열의 범위를 벗어나는 경우) => 누계를 위해 0을 리턴
        if(y<0 || x<0) return 0;
        
        if(DP[y][x]==null) { // 해당 칸에 처음 방문하는 경우
            DP[y][x] = 0; // 우선 0으로 초기화
            if(first.charAt(y) == second.charAt(x)) { // 만약 현재 선택한 두 수열에서의 문자가 같은 경우
                DP[y][x] = recur(y-1, x-1) + 1; // 직전에 구한 최대치에 +1 해라
            }
            else { // 비교하는 두 문자가 다른 경우
                DP[y][x] = recur(y-1, x) >= recur(y, x-1) ? recur(y-1, x) : recur(y, x-1); // 더 최대값인 경우를 입력
            }
        }
        return DP[y][x]; // 최종적으로 구해진 최대값은 이차원 배열 DP의 맨 마지막자리에 입력된 수
    }

---

레퍼런스 코드

참고 링크 : https://infodon.tistory.com/78