[백준] 11053번: 가장 긴 증가하는 부분 수열 (JavaScript)

 

 

 

---

 

문제

https://www.acmicpc.net/problem/11053

 

개념

동적 계획법(DP)

 

 

 

구현 코드(JavaScript)

const fs = require('fs');

// 백준 제출용
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

// 로컬 테스트용
// const filePath =
//   process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
// const input = fs.readFileSync(filePath).toString().trim().split('\n');

const n = Number(input[0]);
const arr = input[1].split(' ').map(Number);

let dp = new Array(n).fill(1);

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

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

 

 

 

 

코드 설명

다이나믹 프로그래밍을 이용해서 풀 수 있는 대표적인 문제입니다.

 

먼저, dp 배열을 n의 크기만큼 설정하고 원소값을 1로 초기화 합니다.

 

이중반복문을 통해 이전 값과 다음 값을 비교할 수 있도록 설정한다면

다음과 같은 dp 점화식을 세울 수 있습니다.

    if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j] + 1);

 

만약 비교하려는 두 수 중 어느 값이 더 크다면, 즉 증가하는 부분 수열(=LIS)이라면

dp[i]는 i번째 원소를 마지막으로 하는 현재 최장 증가 부분 수열의 길이라고 정의합니다. 

dp[i]는 0~i-1번째 원소 중 값은 arr[i]보다 작지만 현재 LIS 길이에 1을 더해줍니다.

 

해당 로직을 통해 현재 최장 증가 부분 수열이 크다면 해당 LIS의 길이를 그대로 유지하고,

아니라면 dp[j] + 1으로 현재 최대 길이에 1을 더해 LIS를 갱신할 수 있습니다.

 

문제에서 주어진 예제 입력은 다음과 같습니다.

6
10 20 10 30 20 50

 

이들을 해당 로직에 적용한 결과는 다음과 같습니다.

 

 

마지막 dp 배열에 결과에 주목해보면 증가하는 부분의 경우 +1로 갱신하는 모습을 볼 수 있습니다.

 

 

---