가장 긴 증가하는 부분 수열

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n] = 수열 A에서 n번째 수가 마지막으로 오는 가장 긴 증가하는 부분 수열의 길이
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 구한다를 이용합니다.
  • 우리가 정의한 dp[n]의 의미에 따르면, dp[n-1]은 A[n-1]을 마지막으로, dp[n-2]는 A[n-2]를 마지막으로, … dp[0]은 A[0]을 마지막으로 가지는 수열의 길이입니다.
  • dp[n]을 결정할 때, dp[n-1], dp[n-2], …, dp[0] 중에서 마지막에 오는 수가 a[n]보다 작으며, 가장 긴 증가하는 부분 수열에 a[n]을 추가하면 됩니다.

문제 풀이 step 2

  • 이 문제의 point는 dp[n]을 A[n]이 마지막으로 오는 부분 수열이라고 정의하는 것입니다.
  • 왜냐하면, 그렇게 정의해야 작은 문제의 해답으로부터 큰 문제의 해답을 구할 수 있기 때문입니다.
    • 증가하는 것을 비교하기 위해서는 각 원소의 대소 비교가 필요합니다.
    • 가장 긴 수열을 구하기 위해서는 각 부분 수열의 길이를 알아야 합니다.
    • Bottom-Up 방식으로 볼 때 {30, 40, 60, 10, 30, 70}일때
    • dp[0] = 1, dp[2] = 2, … 이렇게 아래 단계부터 계산해오면 dp[n]은 구할 수 있습니다.

소스 코드

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

const solution = (input) => {
	const N = parseInt(input[0]);
	const arr = input[1].split(" ").map(Number);
	const dp = Array.from({length: N}, () => 1);

	for (let i = 1; i < N; i++) {
		for (let j = i - 1; j >= 0; j--) {
			if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
				dp[i] = dp[j] + 1;
			}
		}
	}

	return Math.max(...dp);
};

console.log(solution(input));