[JS] 최장부분수열 LIS,LCS

❗️최장 공통 부분 수열 (LCS)

• Longest Common Subsequence
• 두 문자열에서 공통된 부분 수열 중 가장 길이가 긴 것

✅ 구현 방식

• 브루트 포스 방식 : N개의 원소를 가질때 $O(N^2)$ 시간 복잡도를 가짐
• DP 방식 : 반복문을 통해 이차원 배열을 만들어 메모이제이션 진행
  1. 두 수열의 길이 m,n을 통해 m+1,n+1크기의 이차원 배열 만들고 0으로 초기화 (row와 column은 0으로 사용할 기본값)
  2. 두 수열에서 값을 비교

     X[i] === Y[j] 이면 dp[i][j] = dp[i-1][j-1]+1
     X[i] !== Y[j] 이면 dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])

✅ 예시) LCS - 백준 9251번

let dir = __dirname + "/9521.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let x = input[0];
let y = input[1];

let dp = Array.from(Array(x.length + 1), () => Array(y.length + 1).fill(0));

for (let i = 1; i < dp.length; i++) {
  for (let j = 1; j < dp[i].length; j++) {
    if (x[i - 1] === y[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]);
  }
}

console.log(dp[x.length][y.length]);

❗️가장 긴 증가하는 부분 수열 (LIS)

• Longest Increasing Subsequence

✅ 접근 방식

let dp = Array(Math.max(...array)).fill(0); // 배열의 최댓값을 dp의 크기로 둠
let dp = Array(array.length).fill(0); // 배열의 길이를 dp의 크기로 둠

✅ 예시) 가장 긴 증가하는 부분 수열 - 백준 11053번

let dir = __dirname + "/11053.txt";
const path = process.platform === "linux" ? "./dev/stdin" : dir;
const input = require("fs").readFileSync(path).toString().trim().split("\n");

const N = Number(input.shift());
const arr = input[0].split(" ").map(Number);

const dp = Array(N).fill(0);

dp[0] = 1;

for (let i = 1; i < N; i++) {
  let value = arr[i];
  let rest = arr.slice(0, i);
  let tmp = 1;
  for (let j = 0; j < rest.length; j++) {
    if (value > rest[j]) {
      dp[i] = Math.max(dp[j] + 1, tmp);
      tmp = dp[i];
    }
  }
  if (dp[i] === 0) {
    dp[i] = 1;
  }
}
console.log(Math.max(...dp));