[Baekjoon] 9251번 : LCS

1. 문제

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

• DP, LCS 문제

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

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

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

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

// 예제 입력 1
ACAYKP
CAPCAK

// 예제 출력 1
4

2. 핵심 아이디어

• 두 수열이 주어졌을 때, 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾아야 함
• 가장 긴 공통 부분 수열(LCS) 문제로 알려진 대표적인 DP 문제
• 두 수열의 길이가 N 미만일 때, 시간 복잡도 O(N^2)으로 문제를 해결할 수 있음
• D(i)(j) = X(0…i)와 Y(0…j)의 공통 부분 수열의 최대 길이
• 두 문자열의 길이를 조금씩 늘려 가며 확인하여, 공통 부분 수열의 최대 길이 계산
• D(i)(j)
  • D(i-1)(j-1) + 1 => if X(i) = Y(j)
  • max(D(i)(j-1), D(i-1)(j)) => if X(i) != Y(j)

3. Python 문제풀이

import sys
input = sys.stdin.readline

x = input().rstrip()
y = input().rstrip()
dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]

for i in range(1, len(x) + 1) :
  for j in range(1, len(y) + 1) :
    if x[i - 1] == y[j - 1] :
      dp[i][j] = dp[i - 1][j - 1] + 1
    else :
      dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

print(dp[len(x)][len(y)])

4. Java 문제풀이

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

class Main {
  static char[] str1;
  static char[] str2;
  static Integer[][] dp;

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

    str1 = br.readLine().toCharArray();
    str2 = br.readLine().toCharArray();

    dp = new Integer[str1.length][str2.length];
    System.out.println(LCS(str1.length - 1, str2.length - 1));
  }

  static int LCS(int x, int y) {
    if (x == -1 || y == -1) {
      return 0;
    }

    if (dp[x][y] == null) {
      dp[x][y] = 0;

      if (str1[x] == str2[y]) {
        dp[x][y] = LCS(x - 1, y - 1) + 1;
      } else {
        dp[x][y] = Math.max(LCS(x - 1, y), LCS(x, y - 1));
      }
    }
    return dp[x][y];
  }
}