DP를 사용해야할 문제 조건
점화식을 세워 그것을 기반으로 코드를 짠다.
점화식: 인접한 항들 사이의 관계
메모이제이션 + 재귀 함수를 이용해서 풀어나간다. 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하고, 작은 문제들이 해결되었을 때 큰 문제의 답을 얻을 수 있다.
메모이제이션: 계산 결과를 저장. 캐싱이라고도 한다.
// top down DP
let d = new Array(100).fill(0);
function fibo(x) {
if (x === 1 || x === 2) return 1;
// 계산 결과 있으면 반환
if (d[x] !== 0) return d[x];
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
console.log(fibo(99));
DP의 전형적인 형태로 작은 문제를 하나씩 해결해 나가면서 먼저 해결했던 문제들의 값을 이용해서 그 다음 문제를 풀어나간다. (차례대로 문제 해결) 반복문을 이용한다. 결과를 저장하는 리스트를 DP 테이블이라고 한다.
let d = new Array(100).fill(0);
d[1] = 1;
d[2] = 1;
const n = 99;
for (let i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
console.log(d[n]);
DP, 분할 정복 모두 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 사용할 수 있다.
하지만, DP는 각 부분 문제들이 서로 영향을 미치고 부분 문제가 중복되지만 분할 정복 문제(ex. 퀵 정렬)에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
그리디, 구현, 완전 탐색 등 어떤 유형인지 파악한다. 풀이 방법이 떠오르지 않는다면 DP를 고려해본다.
bottom up(상향식) 문제
각 문제는 작은 문제들을 조합해서 해결 가능 & 중복되는 부분 문제를 가진다.
-> 입력 값이 6이라면 5가 1이 되는 최소 연산, 3이 1이 되는 최소 연산, 2가 1이 되는 최소 연산 횟수 3개 중 하나를 선택하여 푼다.
dp[i]
는 i를 1로 만들기 위한 최소 연산 횟수를 저장한다.
const input = require('fs').readFileSync('/dev/stdin').toString();
const num = Number(input);
let cnt = 0;
let dp = [0, 0];
for (let i = 2; i <= num; i++) {
dp[i] = dp[i - 1] + 1;
if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
}
console.log(dp[num]);
입력 조건
(1<=N<=100, 1<=M<=10,000)
출력 조건
예시
예시1
// 입력
2 15
2
3
// 출력
5
예시2
3 4
3
5
7
// 출력
-1
예시3
3 7
2
3
5
풀이
dp[i]
는 i원을 만들기 위한 최소 화폐의 개수i - 화폐단위
원을 만들 수 있다면 i
원도 만들 수 있다.dp
배열을 인덱스가 0인 값 제외하고 모두 INF 값으로 초기화 한다.i - 화폐단위
원을 만들 수 있는지 확인그리디가 아닌 이유: 2, 3원을 이용해 7원을 만들 수 있는 최소 화폐 개수는 2원 2개 3원 1개이다. 즉, 가장 큰 화폐 단위인 3원을 무조건 많이 써서는 구할 수 없다.
const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const MAX = 10001;
const [N, M] = input[0].split(' ').map(Number);
const money = input.slice(1).map(Number);
let dp = new Array(M + 1).fill(MAX);
dp[0] = 0;
for (let i = 0; i < N; i++) {
for (let k = money[i]; k <= M; k++) {
if (dp[k - money[i]] !== MAX) {
dp[k] = Math.min(dp[k], dp[k - money[i]] + 1);
}
}
}
if (dp[M] === MAX) console.log(-1);
else console.log(dp[M]);
결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라.
입력 조건
출력 조건
예시
// 입력
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
// 출력
19
16
풀이
bottom up(상향식)
const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const T = Number(input.shift());
const dx = [-1, 0, 1];
const dy = [-1, -1, -1];
for (let i = 0; i < T; i++) {
const [N, M] = input[i * 2].split(' ').map(Number);
const temp = input[i * 2 + 1].split(' ').map(Number);
let dp = [];
for (let j = 0; j < N; j++) dp.push(temp.splice(0, M));
for (let col = 1; col < M; col++) {
for (let row = 0; row < N; row++) {
let max = 0;
for (let k = 0; k < 3; k++) {
const nx = row + dx[k];
const ny = col + dy[k];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
max = Math.max(max, dp[row][col] + dp[nx][ny]);
}
dp[row][col] = max;
}
}
let ans = 0;
for (let k = 0; k < N; k++) {
if (dp[k][M - 1] > ans) ans = dp[k][M - 1];
}
console.log(ans);
}
array = [4, 4, 5, 8, 4, 11, 15]
-> [4, 5, 8, 11, 15]
dp[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
dp[i] = max(dp[i], dp[j] + 1) if array[j] > array[i]
const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const N = Number(input[0]);
let arr = input[1].split(' ').map(Number);
let dp = new Array(N).fill(1);
for (let i = 1; i < N; i++) {
for (let j = 0; j < i; j++) {
if (arr[j] > arr[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
console.log(N - Math.max.apply(null, dp));