[오늘의 백준 문제] 9252번 LCS 2 - DP

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

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

ACAYKP
CAPCAK

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

4
ACAK

 

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

 

---

✅ 아이디어

• 일단, DP를 활용하여 LCS의 길이를 구한다.
  • dp[i][j] → A의 앞 i글자와 B의 앞 j글자까지 고려했을 때의 LCS의 길이
  • 점화식은 다음과 같다. (bottom-up)
    • A[i] == B[j] 인 경우 → dp[i][j] = dp[i-1][j-1] + 1
    • A[i] != B[j] 인 경우 → dp[i][j] = max(dp[i-1][j], dp[i][j-1])
• 그리고, dp 테이블 역추적을 통해 실제 LCS 문자열을 구한다.

 

✅ 시간 복잡도

• dp[i][j]를 채우는 과정: O(N × M)
• dp 테이블을 역추적하는 과정: O(N + M)
• 전체 시간 복잡도: O(N × M) ≈ O(1,000,000) → 최대 1000 × 1000 → 충분히 빠름!

 

✅ 자바 코드

import java.io.*;

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

        int lenA = A.length;
        int lenB = B.length;

        int[][] dp = new int[lenA + 1][lenB + 1];

        // LCS 길이 구하기 (DP)
        for (int i = 1; i <= lenA; i++) {
            for (int j = 1; j <= lenB; j++) {
                if (A[i - 1] == B[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]);
                }
            }
        }

        // LCS 문자열 찾기 (역추적)
        StringBuilder sb = new StringBuilder();
        int i = lenA, j = lenB;
        while (i > 0 && j > 0) {
            if (A[i - 1] == B[j - 1]) { // 공통 문자면 LCS에 추가, 대각선으로 이동
                sb.append(A[i - 1]);
                i--;
                j--;
            } else if (dp[i - 1][j] >= dp[i][j - 1]) { // 더 큰 값으로 이동
                i--;
            } else {
                j--;
            }
        }

        System.out.println(dp[lenA][lenB]);
        if (sb.length() > 0) System.out.println(sb.reverse()); // 거꾸로 추가했으므로 뒤집어서 출력
    }
}

 

1. LCS 길이 구하기 (dp[i][j])

• 두 문자열을 비교하면서 DP 테이블을 채움
• 두 문자가 같으면 대각선 위 값 +1
• 다르면 위쪽 or 왼쪽 중 큰 값 선택

 

2. LCS 문자열 구하기 (역추적)

• dp[lenA][lenB]에서 시작해서 거꾸로 탐색
• 같은 문자를 만나면, LCS 문자열에 추가 & 대각선 위로 이동
• 다르면, 더 큰 값이 있는 방향으로 이동
• LCS 문자열이 거꾸로 만들어지므로, 마지막에 뒤집어서 출력

 

---

📌 예시

 

1. 입력

ACAYKP
CAPCAK

 

2. DP 테이블

s1 \ s2	-	C	A	P	C	A	K
-	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

3. 출력

4
ACAK

 

 

---

📌 top-down 방식의 경우 (재귀)

        // 초기화 (탑다운 방식)
        for (int i = 0; i <= lenA; i++) {
            for (int j = 0; j <= lenB; j++) {
                dp[i][j] = -1; // 아직 계산되지 않음을 표시
            }
        }
        System.out.println(LCS(lenA, lenB));

...

    // 재귀 함수 (탑다운 방식)
    static int LCS(int i, int j) {
        if (i == 0 || j == 0) return 0; // 문자열이 없는 경우
        if (dp[i][j] != -1) return dp[i][j]; // 이미 계산된 경우

        if (A[i - 1] == B[j - 1]) { // 같은 문자면 대각선 이동
            return dp[i][j] = LCS(i - 1, j - 1) + 1;
        } else { // 다르면 위쪽 또는 왼쪽 중 큰 값 선택
            return dp[i][j] = Math.max(LCS(i - 1, j), LCS(i, j - 1));
        }
    }

• LCS(i, j)는 A[0...i]와 B[0...j]의 LCS 길이를 반환하는 함수
• 메모이제이션 (dp[i][j] 값이 -1이 아닐 경우)으로 중복 계산 방지
• 기저 사례: i == 0 또는 j == 0일 때 LCS 길이는 0