백준 - 11053번 가장 긴 증가하는 부분 수열 (Js, Javascript)

백준 - 11053번 가장 긴 증가하는 부분 수열 문제풀이

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

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

문제는 위의 사진과 같다. 가장 긴 증가하는 부분 수열을 DP 로 풀었다. 

예제를 예를 들어 10, 20, 10, 30, 20, 50 일 시 10, 20, 30, 50 을 선택 시 정답이 4가 나오게 된다

 

먼저 입력으로 배열의 길이를 받는다. 배열의 길이를 받아, 그만큼 현재까지의 수열의 길이를 저장할 배열을 만들어 둔다.

const memorized = new Array(count).fill(1); // 배열을 만들고 내부 값을 모두 1로 초기화 한다

 

[10,20,10,30,20,50] 배열을 이중 for문을 순회하게 되는데, 맨 처음 인덱스는 i = 1, 두번째 안에 있는 for문은 i 전까지의 배열을 확인한다. 예를들어 세번째 요소인 10 차례일 때에는 그 앞의 10, 20 요소들의 검사를 위해 2중 for문을 돌게 된다.

증가하는 수열이므로 3번째 10를 예를 들면, 앞에 10, 20 은 본인보다 큰 값이므로 순회 시 무시한다. 검사조건은 자기보다 작은 수열일 때에만 체크를 하면 된다.

만약에 두번째 20 케이스에는 앞에 10이 20보다 작으므로 이전까지 수열의 길이를 저장한 테이블의 값에 + 1을 한 값과 수열의 길이를 저장한 테이블의 값을 비교하여 큰 값으로 현재까지의 수열의 길이를 저장한 테이블을 업데이트 해준다. 하단의 사진을 참고 부탁드린다.

 

상기 로직을 코드로 옮기면 다음과 같다.

마지막은 수열의 최대값을 구해야 하므로 spread operator 를 사용하여 출력하였다. 

알고리즘의 시간복잡도는 BigO(n^2) 이다. 

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const count = parseInt(input[0]);
const inputList = input[1].split(" ").map((el) => parseInt(el));

const memorized = new Array(count).fill(1);

for (let i = 1; i < count; i++) {
  for (let j = 0; j < i; j++) {
    if (inputList[i] > inputList[j]) {
      memorized[i] = Math.max(memorized[i], memorized[j] + 1);
    }
  }
}

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

 

설명이 부족한 것 같아 댓글로 문의사항이 있을 시, 본문에 추가할 예정이다.