자바스크립트로 보는 DP/동적 계획법

Doozuu·2026년 1월 13일
DP자바스크립트

알고리즘&자료구조 (JS)

목록 보기
35/36

DP는 어떤 알고리즘인가?

DP는 큰 문제를 작은 문제로 쪼개고 그 결과를 저장해서 중복 계산을 없애는 알고리즘이다.


DP는 언제 사용하는가?

1. 최적 부분 구조

큰 문제의 최적해가 작은 문제들의 최적해로 구성된다.
예: n번째 피보나치 -> n-1, n-2의 결과로 결정됨

2. 중복되는 부분 문제

같은 작은 문제가 계속 반복됨
예 : f(3)은 여러 경로에서 계속 호출됨

DP와 그리디의 차이

구분그리디DP
선택지금 당장 최선모든 경우 고려
되돌리기불가가능
빠름매우 빠름상대적으로 느림
정확성조건 안 맞으면 틀림항상 정답

DP로 문제 푸는 방법

예시 문제

  • 한 번에 1칸 또는 2칸 이동 가능
  • 연속으로 3칸은 밟을 수 없음
  • 각 계단에는 점수가 있음
  • 마지막 계단은 반드시 밟아야 함
  • 얻을 수 있는 최대 점수 구하기

1. 상태 정의

dp[i] = i번째 계단까지 도착했을 때 얻을 수 있는 최대 점수

2. 점화식 세우기

i번째 계단에 도착하는 방법은 두 가지뿐이다.

  • i-2 → i (2칸 점프)
    dp[i] = dp[i-2] + score[i]

  • i-3 → i-1 → i (2칸 + 1칸)
    dp[i] = dp[i-3] + score[i-1] + score[i]

  • 최종 점화식

dp[i] = max(
  dp[i-2] + score[i],
  dp[i-3] + score[i-1] + score[i]
)

3. 초기값 설정

idp[i]
dp[1]score[1]
dp[2]score[1] + score[2]
dp[3]max(score[1]+score[3], score[2]+score[3])

4. 작은 것부터 계산

for (let i = 4; i <= N; i++) {
  dp[i] = Math.max(
    dp[i-2] + score[i],
    dp[i-3] + score[i-1] + score[i]
  );
}

관련 문제 풀기

[백준] 2xn 타일링

1x2, 2x1 로 2xn 타일을 채우는 방법의 수를 10007로 나눈 나머지 구하기

  1. 상태 정의
    dp[n] = 2xn 크기 직사각형을 채우는 방법의 수

  2. 점화식 세우기
    dp[n] = dp[n - 2] + dp[n - 1]

  3. 초기값 구하기
    dp[1] = 1, dp[2] = 2

주의 : 결과값에 100007을 나눈 나머지를 반환하는 것이 아니라 중간중간 계산할 때마다 10007로 나눈 나머지를 저장해야 한다. 중간에 JS 정수 범위를 넘어가면 값이 제대로 저장되지 않기 때문이다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const N = +input[0];
const dp = [0];
dp[1] = 1;
dp[2] = 2;

for (let i = 3; i <= N; i++) {
  dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
}

console.log(dp[N]);

[백준] 이친수

이친수란?

  • 0과 1로만 이루어짐
  • 1로만 시작함
  • 1이 연속하지 않음.

  1. 상태 정의
    dp[n] = N자리 이친수의 개수

  2. 점화식 세우기
    dp[n] = dp[n - 2] + dp[n - 1]

  3. 초기값 구하기
    dp[1] = 1, dp[2] = 1

주의 : 숫자가 매우 커져서 정수 표현 한계를 넘을 수 있으므로 BigInt를 이용해준다.
자바스크립트에서 Number 타입으로 표현할 수 있는 정수의 한계는 2^53 - 1 ≈ 9,007,199,254,740,991 으로 이 값을 넘으면 정확한 값을 반환하지 못한다.
따라서 큰 숫자를 정확하게 표현하기 위해 BigInt를 이용해주어야 한다.
숫자를 BigInt로 만드는 법은 BigInt()로 숫자를 감싸거나 숫자 뒤에 n을 붙이면 된다.
BigInt의 타입은 bigint이기 때문에 반환할 때 toString()을 해주어 출력 시 에러를 방지한다.

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const N = +input[0];
const dp = [0];
dp[1] = 1n;
dp[2] = 1n;

for (let i = 3; i <= N; i++) {
  dp[i] = dp[i - 2] + dp[i - 1];
}

console.log(dp[N].toString());

[백준] LCS

  1. 상태 정의
    dp[i][j] = S의 앞 i글자와 T의 앞 j글자의 LCS 길이

  2. 점화식 세우기

  • 마지막 글자가 같을 때 (LCS 길이 + 1)
dp[i][j] = dp[i-1][j-1] + 1
  • 마지막 글자가 다를 때 (이전 문자 중 길이 긴 것)
dp[i][j] = max(
  dp[i-1][j], // S 쪽 문자 버림
  dp[i][j-1]  // T 쪽 문자 버림
)
const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const S = input[0];
const T = input[1];

const n = S.length;
const m = T.length;

// dp[i][j] = S의 앞 i글자, T의 앞 j글자의 LCS 길이
const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= m; j++) {
    if (S[i - 1] === T[j - 1]) {
      // 마지막 문자가 같으면 LCS에 포함
      dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
      // 다르면 하나 버린 경우 중 최대
      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
}

console.log(dp[n][m]);

[백준] 가장 큰 증가하는 부분 수열

  1. 상태 정의
    dp[i] = i에서 끝나는 증가 부분 수열의 최대 합
  2. 점화식 세우기
    dp[i] = max(dp[i], dp[j] + A[i])
const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const N = +input[0];
const arr = input[1].split(" ").map(Number);
const dp = [...arr];

for (let i = 0; i < N; i++) {
  for (let j = 0; j < i; j++) {
    if (arr[i] > arr[j]) {
      dp[i] = Math.max(dp[i], dp[j] + arr[i]);
    }
  }
}

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

[백준] 가장 긴 감소하는 부분 수열

  1. 상태 정의
    dp[i] = i에서 끝나는 가장 긴 감소하는 부분 수열의 길이
  2. 점화식 세우기
    dp[i] = max(dp[i], dp[j] + 1)
const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const N = +input[0];
const arr = input[1].split(" ").map(Number);
const dp = Array(N).fill(1);

for (let i = 0; i < N; i++) {
  for (let j = 0; j < i; j++) {
    if (arr[i] < arr[j]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
}

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

[백준] 동전 2

  1. 상태 정의
    dp[i] = i원을 만들기 위한 동전의 최소 개수
  2. 점화식 세우기
    dp[i] = min(dp[i], dp[i-coins[j]] + 1)
const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./test.txt")
  .toString()
  .trim()
  .split("\n");
const [N, K] = input[0].split(" ").map(Number);
const coins = input.slice(1).map(Number);
const dp = Array(K + 1).fill(Infinity);

dp[0] = 0;

for (let i = 1; i <= K; i++) {
  for (let j = 0; j < N; j++) {
    if (i >= coins[j]) {
      dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
    }
  }
}

console.log(dp[K] === Infinity ? -1 : dp[K]);
profile
Doozuu
모든게 새롭고 재밌는 프론트엔드 새싹
이전 포스트

자바스크립트로 보는 그리디/탐욕법

다음 포스트

자바스크립트로 보는 다익스트라

0개의 댓글