[boj] 11053. 가장 긴 증가하는 부분 수열 (node.js)

문제

[boj] 11053. 가장 긴 증가하는 부분 수열 (node.js)

• 최장 증가 수열 (LIS, Longest Increasing Subsequence) 문제다.

풀이

• 동적 프로그래밍 기법으로 이전 항까지의 최장 수열 길이를 저장해둔 후, 그 결과를 활용하여 각 숫자에서의 최장 부분 수열 길이를 구할 수 있다.
• 특정 수에서의 최장 부분 수열 길이는, (해당 수 앞에 있는 수들 중 이 수보다 작은 수의 인덱스에 저장해둔 최장 수열 길이의 최댓값 + 1) 또는 1 중 더 큰 수이다.

for (let i = 0; i < N; i++) {
  dp[i] = 1;
  for (let j = 0; j < i; j++) {
    if (arr[j] < arr[i]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  result = Math.max(result, dp[i]);
}

생각

• 처음에는 뒤로 가면서 탐색하는 게 더 효율적일 것이라 생각해 단순 완전 탐색으로 풀었으나 틀렸다. 이 경우는 메모이제이션을 통해 이전에 계산해둔 LIS 값에 즉시 접근할 수 있도록 구현하여 앞의 갚을 참조하는 것이 더 효율적이다.

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = input();
  const arr = input().split(" ").map(Number);
  const dp = [];
  if (N == 1) return console.log(1);
  let result = 0;
  for (let i = 0; i < N; i++) {
    dp[i] = 1;
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    result = Math.max(result, dp[i]);
  }
  console.log(result);
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});