[BOJ 9252] LCS2

문제 정리

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제
두 수열이 주어진다.
부분 수열을 찾는다.
그 중 가장 긴 것을 찾는다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
LCS의 길이와 LCS를 출력한다.

제한 사항

0.1s, java11: 0.4s
각 수열 = 최대 1000글자
LCS가 0인 경우, 길이만 출력

핵심 포인트

LCS를 naive하게 찾아보자.

• A 수열과 B 수열이 있을 때, B 수열로 A 수열의 LCS를 찾는다면 O(N^3)이 발생한다.
• B 수열의 각 글자를 첫 부분 수열의 글자로 생각하고 찾는다면 1000 글자에 대해 각 각 1000 - i 글자 수를 연산해야 된다. (N^2)
• 각 N^2의 부분 수열의 글자가 A 수열에 있는지 확인해야한다. (N^3)
• 완전 탐색으로는 불가능 한 것을 알게 됐다.

DP 또는 그리디, 이분 탐색과 같은 효율적인 알고리즘을 선택해야된다.
해당 문제는 유명한 LCS 문제라서 DP인 것은 자명하다.
하지만, 처음 문제를 봤을 때 DP인지 어떻게 알 수 있을까?

키 포인트가 3가지 있다.

1. 부분 수열 -> B 수열 중 앞 부분의 작은 수열에 다음 글자를 추가한다면 메모제이션을 활용할 수 있다.
2. 가장 긴 -> 최장을 찾는 문제에서는 DP를 의심할 수 있다.
3. 시간 제한 -> 채 1초도 안되는 짧은 시간은 선형 탐색이나 상수 탐색에서 주로 나온다. DP를 의심할 수 있다.

핵심 로직

ACAYKP vs CAPCAK DP Table

 

DP 테이블을 그려보면, 그림과 동일하다. ACAYKP 에서 바라보자.

A가 CAPCAK에서 A를 만난 순간부터 LCS는 1이다.

C는 이전에 A의 LCS가 있기 때문에, CAPCAK에서 C를 만나지 못한다면 부분 수열 A의 LCS가 AC의 LCS가 될 것이다.

만약, C를 만난다면 C를 만난 시점(바로 이전 부분 수열)까지의 LCS + 1 개이다.

 

즉 2가지 케이스만 존재하므로 점화식을 도출 할 수 있다.

if ch1 == ch2 DP[i][j] = DP[i-1][j-1] + 1

else DP[i][j] = max(DP[i-1][j], DP[i][j-1])

 

그럼, LCS의 문자를 뽑아내려면 어떻게 할 수 있을까? -> trace

두 수열의 길이부터 시작해서 dp 테이블을 통해 추적 할 수 있다.

 

if (A와 B의 길이가 각각 <= 0) return

else if (문자가 같다면) 문자 저장

else DP 테이블에서 A, B를 통한 경로 중 더 큰 값으로 추적

코드

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    static int[][] dp = new int[1001][1001];
    static String str1, str2;

    public static void main(String[] args) throws IOException {
        str1 = br.readLine();
        str2 = br.readLine();

        for (int i = 0; i < str1.length(); i++) {
            for (int j = 0; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(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]);
                }
            }
        }

        int maxLcsLength = dp[str1.length()][str2.length()];
        sb.append(maxLcsLength).append('\n');
        trace(str1.length(), str2.length());

        bw.write(sb.toString());
        bw.flush();
    }

    static void trace(int s1Idx, int s2Idx) {
        if (s1Idx <= 0 || s2Idx <= 0) {
            return;
        } else if (str1.charAt(s1Idx - 1) == str2.charAt(s2Idx - 1)) {
            trace(s1Idx - 1, s2Idx - 1);
            sb.append(str1.charAt(s1Idx - 1));
        } else if (dp[s1Idx - 1][s2Idx] >= dp[s1Idx][s2Idx - 1]) {
            trace(s1Idx - 1, s2Idx);
        } else {
            trace(s1Idx, s2Idx - 1);
        }
    }

}