[JavaScript][node.js] 백준 11053 가장 긴 증가하는 부분 수열

문제

11053번: 가장 긴 증가하는 부분 수열

 

풀이과정

1차시도

const memo = new Array(n).fill(1);

for (let i = 0; i < n - 1; i++) {
  const start = numbers[i];
  for (let j = i + 1; j < n; j++) {
    memo[j] = start < numbers[j] ? memo[i] + 1 : memo[i];
  }
}

• 이 점화식은, i가 이전보다 낮은 숫자를 가리킬 때 문제가 된다.
• 예를 들어, 10 20 10 20 > 여기서 i=2여서 10을 가리킨다고 해보자.
  • j=3일 때 numbers[i] < numbers[j] 이다.
  • 하지만 이 말이 곧 memo[i]까지의 증가 수열의 끝점(20)보다 numbers[j](20)가 더 크다는 것을 보장하지는 않는다.

 

2차시도

• 그렇다면, 왜 memo[i]까지의 증가 수열의 끝점보다 numbers[j]가 더 크다는 것이 보장되지 않았을까?
• 바로 수열이 작아질 때 그 이유가 있다.
• 예를 들어, 10 20 10 > i=1,j=2라고 가정해 보자.
  • 1차시도 그대로라면, numbers[i]보다 numbers[j]가 더 작기 때문에 memo[2] = memo[1]가 된다.
  • 하지만 보장된 것은 없다. 그냥 이전걸 무시하고 기존 값인 1을 유지하는 것이 더 적당하다.
  • 왜냐하면 이전까지의 길이는 memo[1]에서 아주 잘 저장하고 있기 때문이다.
  • 즉 우리는 memo의 정의를 다시 해야 할 필요가 있다.

memo[i] 란?
i 인덱스까지의 증가하는 수열 길이의 최댓값 ⏩️ i 인덱스를 마지막으로 포함한 증가하는 수열 길이의 최댓값

• 이렇게 되면, i 인덱스까지의 증가수열이 보장되면서, 인덱스 비교 시 값이 크기만 하면 +1을 해주면 된다.

const memo = new Array(n).fill(1);

for (let i = 0; i < n - 1; i++) {
  const start = numbers[i];
  for (let j = i + 1; j < n; j++) {
    if (start < numbers[j]) {
      memo[j] = memo[i] + 1;
    }
  }
}

 

3차시도

• memo[i]가 memo[j]보다 작은 경우를 고려하지 않았다.
• 예를 들어, 10 20 10 30 > i=2, j=3이라고 했을 때,
• memo[2] === 1 (2 인덱스를 마지막으로 포함한 증가하는 수열 길이의 최댓값은 1이다. 이미 2 인덱스가 기준이 된 이상 memo[2]는 값이 확정되었다. j는 기준 인덱스+1부터 시작하므로!)
• 하지만 이미 i=1기준에서부터, memo[3]은 3 이라는 값을 갖고 있었다! 즉 memo[i]보다 memo[j]가 더 큰 상황. 이런 경우를 고려해서 점화식을 수정해야 한다.

const memo = new Array(n).fill(1);

for (let i = 0; i < n - 1; i++) {
  const start = numbers[i];
  for (let j = i + 1; j < n; j++) {
    if (start < numbers[j]) {
      memo[j] = Math.max(memo[j], memo[i] + 1);
    }
  }
}

 

최종코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

const input = fs.readFileSync(filePath).toString().trim().split('\n');
const n = +input[0];
const numbers = input[1].split(' ').map(Number);
const memo = new Array(n).fill(1);

for (let i = 0; i < n - 1; i++) {
  const start = numbers[i];
  for (let j = i + 1; j < n; j++) {
    if (start < numbers[j]) {
      memo[j] = Math.max(memo[j], memo[i] + 1);
    }
  }
}

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

 

후기

• DP만 보면 토할 것 같다... 그래도 DP는 풀때마다 점화식을 유도해내는 과정을 적어보자!