DP(동적 계획법)
DP를 사용해야할 문제 조건
- 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답으로 큰 문제를 해결
- 동일한 작은 문제를 반복적으로 해결
구현 방식
점화식을 세워 그것을 기반으로 코드를 짠다.
점화식: 인접한 항들 사이의 관계
top-down(하향식)
메모이제이션 + 재귀 함수를 이용해서 풀어나간다. 큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하고, 작은 문제들이 해결되었을 때 큰 문제의 답을 얻을 수 있다.
메모이제이션: 계산 결과를 저장. 캐싱이라고도 한다.
// 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));bottom-up(상향식)
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 vs 분할 정복
DP, 분할 정복 모두 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 사용할 수 있다.
하지만, DP는 각 부분 문제들이 서로 영향을 미치고 부분 문제가 중복되지만 분할 정복 문제(ex. 퀵 정렬)에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
DP 문제 접근 방법
그리디, 구현, 완전 탐색 등 어떤 유형인지 파악한다. 풀이 방법이 떠오르지 않는다면 DP를 고려해본다.
문제
1로 만들기
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]);효율적인 화폐구성
- N가지 종류의 화폐가 있다.
- 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.
이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
입력 조건
- 첫째 줄에 N, M이 주어진다.
(1<=N<=100, 1<=M<=10,000) - 이후의 N개의 줄에서는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.
출력 조건
- 첫째 줄에 최소 화폐 개수를 출력한다.
- 불가능할 때는 -1을 출력한다.
예시
예시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 테이블인
dp배열을 인덱스가 0인 값 제외하고 모두 INF 값으로 초기화 한다. - 각각의 화폐 단위에 대해서
i - 화폐단위원을 만들 수 있는지 확인 - bottom up(하향식)
그리디가 아닌 이유: 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]);금광
- n X m 크기의 금광이 있다. 금광은 1 X 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있다.
- 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다.
결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하라.
입력 조건
- 첫째 줄에 테스트 케이스 T 입력 (1<=T<=1000)
- 매 테케 첫째 줄에 n과 m이 공백으로 구분되어 입력된다. (1<=n, m<=20) 둘째 줄에 n x m 개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다. (1<=각 위치에 매장된 금의 개수 <=100)
출력 조건
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다. 각 테케는 줄 바꿈을 이용해서 구분한다.
예시
// 입력
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);
}병사 배치하기
- 기본 아이디어: 가장 긴 증가하는 부분 수열(LIS, 전형적인 DP문제 아이디어와 동일)
->array = [4, 4, 5, 8, 4, 11, 15]->[4, 5, 8, 11, 15]
-> 이 문제는 가장 긴 감소하는 부분 수열을 찾는 것 dp[i] = array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이
-> 점화식: 모든 0<=j<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));