문제 개요

문제: LCS 2

분류: DP

난이도: 골드4

문제 풀이

LCS의 길이는 DP를 사용하여 구했고 LCS는 재귀 함수를 사용하여 구했다.

LCS의 길이

문자열 A의 인덱스를 i, 문자열 B의 인덱스를 j라고 했을 때 dp[i][j]는 우선 왼쪽과 위쪽 중 더 큰 값으로 초기화 한다.
그리고 A[i]와 B[i]가 같은 경우, 초기화한 값과 대각선 왼쪽 위의 값(=A[i-1]과 B[j-1]까지 비교했을 때 LCS의 길이)에 1을 더한 값 중 더 큰 값으로 dp[i][j]를 업데이트 한다.

모든 문자에 대해 비교를 끝내면 dp[A.length-1][B.length-1]에 LCS의 길이가 저장된다.

LCS

dp 배열의 마지막 칸에서 시작하여 재귀 함수 호출을 통해 LCS를 구한다.
LCS의 길이가 n이라면 숫자가 처음 n으로 증가한 행, 열을 찾아 해당 알파벳을 LCS 변수에 추가하는 것이다.

현재 행을 a, 열을 b라고 했을 때 아래를 수행한다.

• n이 0이면 return 한다.
• 위쪽 칸이 n인 경우, 위쪽 행으로 이동한다.
  → getLCS(a-1, b, n);
• 왼쪽 칸이 n인 경우, 왼쪽 열로 이동한다.
  → getLCS(a, b-1, n);
• 둘 다 n이 아닌 경우, 현재 칸이 숫자가 처음 n으로 증가한 칸이라는 의미이므로 n을 1만큼 감소시키고 대각선 왼쪽 위로 이동한다.
  → getLCS(a-1, b-1, n);

마지막 문자부터 첫 문자까지 거슬러 올라갔으므로 위 과정에서 구한 LCS는 reverse하여 출력해야 한다.

아래 그림은 문제에서 주어진 예제 입력1에서 LCS를 구하는 과정이다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [A, B] = fs.readFileSync(filePath).toString().trim().split("\n");

const solution = (A, B) => {
  const dp = Array.from({ length: A.length + 1 }, () =>
    new Array(B.length + 1).fill(0)
  );
  const lenA = A.length;
  const lenB = B.length;

  for (let i = 1; i <= A.length; i++) {
    for (let j = 1; j <= B.length; j++) {
      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      if (A[i - 1] === B[j - 1])
        dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
    }
  }

  let lcs = [];

  const getLCS = (a, b, n) => {
    if (n === 0) return;

    // 숫자가 처음 n으로 증가한 행, 열을 찾아 해당 알파벳을 lcs에 추가한다.
    if (dp[a - 1][b] === n) getLCS(a - 1, b, n);
    else if (dp[a][b - 1] === n) getLCS(a, b - 1, n);
    else {
      lcs.push(A[a - 1]);
      getLCS(a - 1, b - 1, n - 1);
    }
  };

  getLCS(lenA, lenB, dp[lenA][lenB]);

  console.log(dp[lenA][lenB]);
  console.log(lcs.reverse().join(""));
};

solution(A, B);