[백준11053_자바스크립트(javascript)] - 가장 긴 증가하는 부분 수열

🔴 문제

가장 긴 증가하는 부분 수열

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, inputs] = fs.readFileSync(path).toString().trim().split('\r\n');
const A = inputs.split(' ').map(Number);
const dp = new Array(Number(n)).fill(1);

for (let i = 1; i < Number(n); i++) {
  for (let j = 0; j < i; j++) {
    if (A[i] > A[j]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}

console.log(Math.max(...dp));

🟢 풀이

⏰ 소요한 시간 : -

유튜브 풀이를 보고 이해하긴 했는데 유튜브에서 제출한 답안대로 js로 제출하면 틀렸습니다가 뜸... gpt의 도움을 받았다.
이 문제는 dp로 풀수도 있고 이분탐색으로 풀 수도 있다고 하는데 나는 이분탐색을 학습하지 않았으므로 dp로 풀이한다.

dp 배열은 각 위치에서의 가장 긴 증가하는 부분 수열 LIS(Longest Increasing Subsequence)의 길이를 저장한다.
즉 dp[i]는 arr[i]를 마지막 원소로 하는 LIS의 길이를 나타낸다. dp 배열의 각 원소 자체로 이루어진 LIS의 길이는 1이기 때문에 모든 값은 1로 초기화 해준다.
이후 배열을 순회하게 되는데 dp[0]을 마지막 원소로 하는 LIS는 1이기에 i는 1부터 순회를 해준다.
i가 1일때 j는 0번째 요소부터 현재 타겟인 i의 바로 앞 요소까지 확인하면서 A[i] > A[j] 일 경우, 즉 증가하는 양상일 경우만 dp[i]의 값을 업데이트 해주면 되는데 이 때 기존 자기가 가지고 있는 값과 비교하고있는 대상인 j번째 요소의 LIS에 1을 더한값 중 큰 값으로 업데이트 해주면 된다.

순회를 모두 마치고 dp 배열에서 가장 큰 값을 찾으면 그것이 LIS의 길이가 된다.

문제를 다 풀었지만 헷갈리기도 하고 이 문제 유형은 비슷한 유형이 많아 계속 복습해야겠다.

🔵 Ref

https://www.youtube.com/watch?v=6QkmRvHMfqs