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

++문제문제

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

 

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

예제 입출력

 

입력	출력
6 10 20 10 30 20 50	4

 

풀이[node.js]

 

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString().split('\n');
var cases = Number(inputs[0]);
var inputs = inputs[1].split(' ').map(v=>Number(v));
var dp = new Array(cases).fill(0);
for(var i=0; i<cases; i++){
    var max = 0;
    for(var j=0; j<i; j++){
        if(inputs[i] > inputs[j] && dp[j] > max){
            max = dp[j];
        }
    }
    dp[i] = max + 1;
}
console.log(Math.max(...dp));

 

 

dp를 어떻게 이용해야하는지 감도 안오던 문제였다.

먼저 각각의 inputs값에 0을 채워준다.

그리고 인덱스 0부터 5까지 돌면서 각각의 값이 앞의 숫자들보다 작은지 큰지 비교를 한다.

i가 20이고, j가 10인 경우에는 i값이 더 크다. 기본적으로 max값은 0이지만, i값이 더 크기 때문에, 더 작은 값인 j값의 dp값을 max에 넣어준다. 

이렇게 만약 앞의 값보다 해당 인덱스 값이 크다면 앞의 값의 dp값을 구해서 max값에 넣어준다.

해당 인덱스값보다 작은 값들의 dp를 다 돌면서, max값을 설정해주고, 해당 인덱스의 dp값은 max값에서 1을 더해준 값으로 지정해주면 된다.

여기서 주의할 점은, inputs의 i값이 j값보다 크다고 해서 무조건 max값을 해당 dp의 j값을 입력해주면 안된다.

그럴 경우에는 최대값이 max값으로 대입되는 것이 아니라, 가장 마지막에 들어온 dp[j]값이 max값으로 설정되기 때문이다.

30을 예로 들자면, 10, 20, 10이 모두 30보다 작다.

dp[j] > max로 설정해주지 않는다면, 가장 마지막 dp[j]값인 1이 max값이 되어 30의 dp값이 1+1인 2가 되버린다.

그렇기에, dp[j]가 max보다 큰지 확인하고, 더 큰 값이라면 그 값을 dp[j]로 설정해준다.

 

출처: https://leylaoriduck.tistory.com/524

 

문제를 풀다가 이런 질문을 봤다. 피보나치 문제처럼 dp(i)에 dp(i-1)이나 dp(i-2)가 관여하지 않는데 왜 DP문제인가요? 나도 이런 생각을 했는데, dp의 핵심은 하나의 문제를 여러 하위 문제로 나누어 풀고, 그 과정 중에서 중복적인 계산을 줄이기 위해 하위 계산의 결과를 저장하는 메모제이션이라고 생각한다.

따라서 방금 문제의 경우에도 만약 우리가 최대 부분 증가 수열의 길이를 저장하는 배열을 따로 두지않았더라면 반복문의 매 i 번째 마다 0부터 i 번째까지의 부분 수열들의 길이를 비교하는 계산을 했어야 할 것이다.

하지만 메모제이션을 통해 그 결과들을 저장해두었고 우리는 i번째마다 그 이전의 부분 수열 중 최대값이 i번째 값마다 작고 제일 긴 부분 증가수열을 가져옴으로서 dp알고리즘으로 문제를 푼 것이 되는 것이다.

 

출처: https://amunre21.github.io/boj/11053/

백준 11053번: 가장 긴 증가하는 부분 수열 - javascript