백준 11053 < 가장 긴 증가하는 부분 수열 > JavaScript

📍문제 링크

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

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

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

- 가장 긴 증가하는 부분수열 : LIS (Longest Increasing Subsequence) 알고리즘으로 알려져 있다

- DP를 사용하여 해결한다

- 비슷한 문제가 많은 시리즈 문제

- LIS의 길이만 다루면 됨

- memo 배열을 data[n] 까지의 LIS 길이를 저장하는 배열로 사용

 

📍의사 코드

- LIS 길이를 저장할 memo 배열을 만듬

- memo[0] = 1 이므로,  초기값 할당

- memo[0]은 있으므로 index 1 ~ N 미만 까지의 반복문생성 (n-1번 시행)

- memo[i] = 1 (최솟값) 할당

- 중첩 반복문을 만들고 값이 증가하는 경우에만 memo[i]에 +1 실행후 업데이트

 

📍코드 (JavaScript)

const [in1, in2] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const tNum = +in1;
const data = in2.split(" ").map(Number);
const memo = [1];

for (let i = 1; i < tNum; i++) {
  memo[i] = 1;
  for (let j = 0; j < i; j++) {
    if (data[j] < data[i]) {
      memo[i] = Math.max(memo[j] + 1, memo[i]);
    }
  }
}

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

 

📍리뷰

- 이해할 때 참조한 반례

// 6
// 1 2 1 1 1 3
// 1 2 1 1 1 3 <- memo

// 7
// 8 9 10 1 2 3 4
// 1 2 	3 1 2 3 4 <- memo