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

백준 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

접근

0부터 N번째까지의 부분 증가 수열의 최대길이를 구하는 문제다. 예시로 나온 배열로 생각해보자.

i = 0 일때

배열 값	10	20	10	30	20	50
최대길이	1	0	0	0	0	0

0번째 값보다 작은수는 없으므로 최대 길이는 1이다

i = 1 일때

배열	10	20	10	30	20	50
최대길이	1	2	0	0	0	0

1번쨰까지 배열 중 1번째 값보다 작은 수는 10하나가 있는데 10까지의 최대 부분증가 수열의 길이는 1이므로 1 + 1 = 2가된다.

i = 2 일때

배열	10	20	10	30	20	50
최대길이	1	2	1	0	0	0

2번째까지 배열 중 2번째 값보다 작은 수는 없으므로 i = 2의 최대 부분 증가 수열의 길이는 1이다.

i = 3 일때

배열	10	20	10	30	20	50
최대길이	1	2	1	3	0	0

3번째까지 배열 중 3번째 값인 30보다 작은 수는 10, 20, 10 전부 해당된다. 이 중에서 20까지의 부분증가 수열 길이인 2가 제일 크기때문에 2 + 1 = 3으로 30까지의 최대 부분 증가 수열의 길이는 3이 된다.

결론

배열	10	20	10	30	20	50
최대길이	1	2	1	3	2	4

위와 같은 방식으로 진행하다보면 20은 최대 2, 마지막 수인 50은 앞서나온 수열 중 최대 길이인 3과 더해서 길이가 4인 부분 증가 수열이 된다.

이렇게 해서 구해진 최대길의 배열의 max 값을 구하면 된다.

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

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

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

++javascript로 풀때 잘 봐야할 점

javascript는 변수를 선언할 때 데이터 타입을 직접 언급하지 않는다. 따라서 이번과 같은 문제를 풀때 두번째 입력값인 whitespace로 이루어진 배열을

let array = input[0].split(' ')
array.reduce((acc,cur)=>{
  let tmp = 1;
  if(cur<tmp){
    blablabla
  }
})

의 형식으로 입력받아서 사용하게 되는데, 이때 다행히 곱연산이나 for loop문으로 계산하기 되면 운좋게 넘어갈 수 도 있지만, 나처럼 reduce를 활용하여 직접 배열 값을 활용하는 경우 string형으로 인식되어있어서 오류가 날 수 도있다.

심지어 예제는 전부 10의 배수여서 string으로 이루어진 숫자도 유니코드 순으로 비교하는 javascript에서는 위처럼 cur과 tmp를 비교하게되면 javascript는 1이 10보다는 크고 20보다는 작다고 결과를 도출 할 것이다.

코드 잘 짜놓고도 틀릴 수 있는 문제점이다. 항상 숫자 연산 비교가 필요하면 비교변수를 *1이나 parseInt()를 이용해서 숫자로 바꿔주자.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let arr = input[1].split(' ');
  let answer = max_sub_dp(arr);
  console.log(answer);
  process.exit();
});

function max_sub_dp(arr){
  let max_sub = arr.reduce((acc,cur,idx,arry)=>{    
    let tmp = [];
    for(let i = 0 ; i<idx+1;i++){      
      if(arry[i]<parseInt(cur)){
        tmp.push(acc[i])
      }
    }    
    if(tmp.length>0){
      acc[idx] += Math.max(...tmp);
    }    
    return acc;
  },Array(arr.length).fill(1));    
  return Math.max(...max_sub);
}