백준 9251 < LCS > JavaScript

📍문제 링크

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

9251번: LCS

 

📍알고리즘 분류

- 다이나믹 프로그래밍

- 문자열

 

📍문제 풀이

- 다이나믹 프로그래밍(DP) 관련해서 유명한 문제

- X, Y 두 수열이 주어졌을 때, 두 수열의 최장 공통 부분 수열을 구해보자

예시)

LCS(X,Y) = B C B A
  _ _ _   _
A B C B D A B
_   _   _ _
B D C A B A

- 단순 무식하게 브루트 포스 방식으로 푼다면 X의 모든 부분 수열을 구하고, 이 중에서 Y의 부분 수열이 되는 것을 구한뒤, 가장 길이가 긴 것을 구하면 된다.

- 하지만 부분 수열을 구하는데는 X가 N개의 원소를 가질 떄, O(2^N) 의 시간 복잡도를 가진다.

- 시간이 너무 오래걸려서 적합하지 않다

 

- DP를 사용하면 빠르게 문제를 해결할 수 있다.

- [ x(1) ], [ y(1) ] 을 비교하여 원소가 같으면 LCS의 길이를 1 늘리고,

- 원소가 다르면 [ x(1) ],  [ y(1), y(2) ] 와 [ x(1), x(2) ],  [ y(1) ] 의 LCS 길이 중 큰 것을 답으로 취한다.

- 반복문을 통해 이차원 배열을 만들어 최종 출력할 답을 만들어가고, 이는 메모이제이션으로 빠르게 진행된다.

 

📍의사 코드 (tabulation, bottom-up 방식)

- 두 수열의 길이 m, n을 통해 m + 1 * n + 1 크기의 이차원 배열 memo를 만들고 0으로 채운다

인덱스 0인 row 와 column은 0으로 사용할 기본값이므로 전체 길이를 m + 1 * n + 1 크기로 설정한다

 

- 중첩 반복문으로 이차원 배열을 순회하는데

두 수열에서 X[i] === Y[j] 이면, memo[i - 1][j - 1] + 1의 값을 memo[i][j] 에 기록한다

두 수열에서 X[i] !== Y[j] 이면, memo[i][j-1] 과 memo[i - 1][j] 중에서 큰 값을 memo[i][j] 에 기록한다

 

-  반복문이 끝나면 memo[m + 1][n + 1] 값을 출력한다

 

📍코드 (JavaScript)

const [X, Y] = require('fs')
  .readFileSync('/dev/stdin')
  .toString()
  .trim()
  .split('\n');

const lcs = (x, y) => {
  const [m, n] = [x.length, y.length];
  const memo = Array.from({ length: m + 1 }, (_) =>
    Array.from({ length: n + 1 }, (_) => 0)
  );
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (x[i - 1] === y[j - 1]) memo[i][j] = memo[i - 1][j - 1] + 1;
      else memo[i][j] = Math.max(memo[i - 1][j], memo[i][j - 1]);
    }
  }
  console.log(memo[m][n]);
};

lcs(X, Y);