[백준] 11053. 가장 긴 증가하는 부분 수열 (자바스크립트/javascript/node.js/동적계획법/동적 프로그래밍/다이나믹 프로그래밍)

 

문제를 풀기 위한 아이디어

일단 "가장 긴 증가하는 부분 수열" 이라는 것은 주어진 수열 내에서 공차, 공비 이런 것은 신경쓰지 않고 단순히 증가하는 양상만 보았을 때 어떤 부분 수열(쉽게 말해서 부분 집합)이 가장 긴 가를 따지는 것이다.

 

우선 dp값을 저장할 배열을 주어진 수의 길이인 N 사이즈에 맞게 만들고 초기 값을 모두 1로 채워준다.

dp[N]에는 N까지의 배열에서 가장 긴 증가하는 부분 수열의 길이가 저장될 것이다.

이 때 초기값을 1로 채워주는 이유는, 최소한 자기 자신은 다 가지고 있기 때문에 1로 채워주는 것이다.

 

그리고 문제에서 주어진 수열을 numbers라는 배열에 저장하고,

각 numbers를 반복문을 돌며 자기 자신보다 작은 값을 세야 한다.

numbers = [100, 200, 0, 1, 7, 300, 500]으로 예를 들어보자.

 

1. dp[0]

우선 첫번째 요소인 100은 반복문을 돌 필요가 없으므로 dp[0] = 1 (위에서 초기에 저장된 값임)

   => dp[0] = 1

2. dp[1]

자기보다 앞에 있는 요소들과 비교한다.

1) if(numbers[0] < numbers[1]) => O

  → 여기서 numbers[0]이 numbers[1]보다 작다는 것은 dp[0]에 numbers[1]을 붙일 수 있다는 말이 된다. 그러므로 dp[1] = dp[0] + 1 = 2가 된다.

  => dp[1] = 2

3. dp[2]

자기보다 앞에 있는 요소들(dp[0], dp[1])과 비교한다.

1) if(numbers[0] < numbers[2]) => X

2) if(numbers[1] < numbers[2]) => X

자신보다 작은 값이 없기 때문에 dp[i] 는 초기값 1에서 변함이 없다. dp[2] = 1

  => dp[2] = 1

 

4. dp[3]

자기보다 앞에 있는 요소들(dp[0], dp[1], dp[2])과 비교한다.

1) if(numbers[0] < numbers[3]) => X

2) if(numbers[1] < numbers[3]) => X

3) if(numbers[2] < numbers[3]) => O

→ 여기서 numbers[2]가 numbers[3]보다 작다는 것은 dp[2]에 numbers[3]을 붙일 수 있다는 말이 된다. 그러므로 dp[3] =  dp[2] + 1 = 2가 된다.

  => dp[3] = 2

 

5. dp[4]

자기보다 앞에 있는 요소들 (dp[0], dp[1], dp[2], dp[3])과 비교한다.

1) if(numbers[0] < numbers[4]) => X

2) if(numbers[1] < numbers[4]) => X

3) if(numbers[2] < numbers[4]) => O

→ 여기서 numbers[2]가 numbers[4]보다 작다는 것은 dp[2]에 numbers[4]을 붙일 수 있다는 말이 된다. 그러므로 dp[4] =  dp[2] + 1 = 2가 된다.

4) if(numbers[3] < numbers[4]) => O

→ 여기서 numbers[3]이 numbers[4]보다 작다는 것은 dp[3]에 numbers[4]을 붙일 수 있다는 말이 된다. 그러므로 dp[4] =  dp[3] + 1 = 3이 된다.

위의 값들 중 최댓값인 3을 저장한다. 따라서 dp[4] = 3

  => dp[4] = 3

... 이렇게 마지막 요소까지 하면 된다!

 

 

내가 작성한 코드 (자바스크립트)

let fs = require("fs");
let numbers = fs.readFileSync("예제.txt").toString().split("\n");
const N = Number(numbers[0]);
numbers.shift();
numbers = numbers[0].split(" ").map((element) => Number(element));

const dp = new Array(N).fill(1);
for (let i = 1; i < N; i++) {
  const values = [1];
  for (let j = 0; j < i; j++) {
    if (numbers[i] > numbers[j]) {
      values.push(dp[j] + 1);
    }
  }
  dp[i] = Math.max(...values);
}
console.log(Math.max(...dp));