LCS

문제링크

LCS

아이디어

• 문자열 S, T 에 대해서 최장 공통 부분 수열의 길이를 구하는 방법에 대해서 생각해봅시다.
  • 문자열 S의 substring => \(S_0\) ~ \(S_i\)
  • 문자열 T의 substring => \(T_0\) ~ \(T_j\)
  • 전체 string의 공통 부분 수열은 substring의 최적해들로 구성되는 것을 알 수 있습니다.
    • substring과 전체string과의 연관성을 찾아봅시다.
• 상태 (i, j, count) 를 아래와 같이 sementic하게 지어줍니다.
  • \(S_i\), \(T_j\) 를 고려하였을 때, 현재까지 구한 최장 부분 수열의 길이(=count)
• 새로운 위치 (i, j)에 대해서 2가지 경우로 구분됩니다.
  • \(S[i] == T[j]\) 일 경우 count값을 증가시켜서 \((i+1,j+1, count+1)\) 로 상태를 전이
  • \(S[i] \neq T[j]\) 일 경우 \((i+1, j, count)\) 또는 \((i, j+1, count)\) 로 전이
    • 이렇게 상태를 전이시키는 이유는 새로운 공통 부분 수열이 S의 새 원소를 포함하는지, T의 새 원소를 포함하는지에 대한 여부를 현재 상태로는 알 수 없기 때문입니다.

소스코드(시간초과)

import java.util.*;
import java.io.*;

public class BOJ_9251 {

    static String S, T;
    static int dfs(int i, int j, int count) {
        if (i == S.length() && j == T.length()) {
            return count;
        }

        int result = count;
        if (i < S.length() && j < T.length() && S.charAt(i) == T.charAt(j)) {
            return dfs(i + 1, j + 1, count + 1);
        } else {
            if (i + 1 < S.length()) {
                result = Math.max(result, dfs(i + 1, j, count));
            }
            if (j + 1 < T.length()) {
                result = Math.max(result, dfs(i, j + 1, count));
            }
            return result;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine();
        T = br.readLine();

        System.out.println(dfs(0, 0, 0));
    }

}

정답 소스코드1(하향식)

\((i, j) \rightarrow (i + 1, j) \text{ or } (i, j + 1)\) 은 중복되는 상태들이 많이 발생한다는 것을 직관적으로 알 수 있습니다. 이를 개선하기 위해서 \(S_i\) \(T_j\) 까지 문자열을 고려하였을 때, 가장 긴 공통 부분 수열의 길이를 메모이제이션해두는 것이 좋습니다.

import java.util.*;
import java.io.*;

public class BOJ_9251 {

    static String S, T;
    static int[][] dp;

    static int dfs(int i, int j) {
        if (i == S.length() || j == T.length())
            return 0;

        if (dp[i][j] != -1)
            return dp[i][j];

        if (S.charAt(i) == T.charAt(j)) {
            return dp[i][j] = 1 + dfs(i + 1, j + 1);
        }

        int result = 0;
        if (i + 1 <= S.length() - 1) {
            result = Math.max(result, dfs(i + 1, j));
        }
        if (j + 1 <= T.length() - 1) {
            result = Math.max(result, dfs(i, j + 1));
        }
        return dp[i][j] = result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        S = br.readLine();
        T = br.readLine();

        dp = new int[S.length()][T.length()];
        for (int i = 0; i < S.length(); i++) {
            Arrays.fill(dp[i], -1);
        }

        // dp[i][j] := [S_i, S_n] / [T_j, T_m] 까지의 문자열의 최장 공통 부분 수열의 길이
        dfs(0, 0);
        System.out.println(dfs(0, 0));
    }

}

정답 소스코드2(정답)

탐색 순서를 상향식으로 구성하는 순서가 간단하므로 점화식으로도 쉽게 표현할 수 있습니다. 점화식은 다음과 같이 세울 수 있습니다. \(dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } S[i] = T[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{if } S[i] \neq T[j] \end{cases}\)

import java.io.*;
import java.util.*;

public class BOJ_9251 {

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

    public static void main(String[] args) throws IOException {
        String S, T;
        S = br.readLine();
        T = br.readLine();

        int[][] dp = new int[S.length() + 1][T.length() + 1];
        dp[0][0] = 0;
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                if (S.charAt(i - 1) == T.charAt(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]);
                }
            }
        }
        System.out.println(dp[S.length()][T.length()]);
    }
}