Algorithm/Javascript로 정리하는 이코테
[Javascript로 정리하는 이코테] 7. 다이나믹 프로그래밍
반응형
http://www.yes24.com/Product/Goods/91433923
개념
- 다이나믹 프로그램은 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘
- 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법
- 다이나믹 프로그래밍을 사용하기 위해서는, 다음 두 조건을 만족해야 한다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
- 다이나믹 프로그램을 구현하는 방식은 두 가지가 있다.
Top-Down
: 재귀적으로 구현 (w/ 메모이제이션)Bottom-Up
: 반복문으로 구현 (w/ DP 테이블)
- 시간복잡도:
O(n)
참고) 자세한 문제 풀이 전략은 여기를 참고하자.
💡 다이나믹 프로그래밍 유형 파악하기
- 특정 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면, 해결하고자 하는 부분 문제들의 중복 여부를 확인해 다이나믹 프로그래밍을 적용할 수 있는지 알아보자.
- 일단 재귀 함수를 구현 한 뒤, 메모이제이션을 적용할 수 있으면 코드를 개선해 나아가는 방법도 좋다.
- 스택 오버플로우를 방지하기 위해 가능한
Bottom-Up
방식으로 구현하자.
예제 8-1. 피보나치 함수
동일한 함수가 반복적으로 호출된다 → O(2^n)
const fibo = (x) => {
if (x === 1 || x === 2) return 1;
return fibo(x - 1) + fibo(x - 2);
};
console.log(fibo(4));
예제 8-2. 피보나치수열 (재귀적)
한 번 구한 정보를 배열에 저장한다 → O(n)
let d = [...Array(100).fill(0)];
const fibo = (x) => {
if (x === 1 || x === 2) return 1;
if (d[x] != 0) return d[x];
return (d[x] = fibo(x - 1) + fibo(x - 2));
};
console.log(fibo(4));
예제 8-3. 호출되는 함수 확인
let d = [...Array(100).fill(0)];
const fibo = (x) => {
console.log(`f(${x})`);
if (x === 1 || x === 2) return 1;
if (d[x] != 0) return d[x];
return (d[x] = fibo(x - 1) + fibo(x - 2));
};
fibo(6);
예제 8-4. 피보나치 수열 (반복적)
보텀업 방식으로 구현 → O(n)
const n = 99;
let d = [...Array(n + 1).fill(0)];
const fibo = (x) => {
d[1] = d[2] = 1;
for (let i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
return d[x];
};
console.log(fibo(n));
실전 문제
1로 만들기
방법 1. Top-Down
const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim();
const n = +input;
const d = [...Array(n + 1).fill(0)];
const dp = (x) => {
if (x === 1 || x === 2 || x === 3 || x === 5) return 1;
if (d[x] !== 0) return d[x];
if (x % 5 === 0) return (d[x] = Math.min(dp(x / 5), dp(x - 1)) + 1);
if (x % 3 === 0) return (d[x] = Math.min(dp(x / 3), dp(x - 1)) + 1);
if (x % 2 === 0) return (d[x] = Math.min(dp(x / 2), dp(x - 1)) + 1);
return (d[x] = dp(x - 1) + 1);
};
function solution(n) {
return dp(n);
}
console.log(solution(n));
방법 2. Bottom-Up
const dp = (x) => {
d[1] = d[2] = d[3] = d[5] = 1;
d[4] = 2;
for (let i = 6; i <= x; i++) {
d[i] = d[i - 1] + 1;
if (i % 2 === 0) d[i] = Math.min(d[i / 2], d[i - 1]) + 1;
if (i % 3 === 0) d[i] = Math.min(d[i / 3], d[i - 1]) + 1;
if (i % 5 === 0) d[i] = Math.min(d[i / 5], d[i - 1]) + 1;
}
return d[x];
};
개미 전사
- i번째 식량 창고를 털지 안 털지 결정하고 최댓값을 구하면 된다.
d[i]
는 i번째 식량 창고에 도달했을 때 털 수 있는 최대 식량을 의미한다.
const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');
let [n, arr] = input;
n = +n;
arr = arr.split(' ').map((v) => +v);
const d = [...Array(n + 1).fill(0)];
const dp = (n) => {
d[0] = arr[0];
d[1] = Math.max(arr[0], arr[1]);
for (let i = 2; i < n; i++) {
d[i] = Math.max(d[i - 2] + arr[i], d[i - 1]);
}
return d[n - 1];
};
function solution(n, arr) {
return dp(n);
}
console.log(solution(n, arr));
바닥 공사
d[i]
는 가로가 i일 때 바닥을 채우는 방법의 수를 의미한다.
const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim();
const n = +input;
const DIV = 796796;
const d = [...Array(n + 1).fill(0)];
const dp = (n) => {
d[1] = 1;
d[2] = 3;
for (let i = 3; i <= n; i++) {
d[i] = (d[i - 2] * 2 + d[i - 1]) % DIV;
}
return d[n];
};
function solution(n) {
return dp(n);
}
console.log(solution(n));
효율적인 화폐 구성
d[i]
는 i원을 만들기 위한 최소한의 화폐 개수이며,d[i]=Infinity
인 경우 i원을 만들 수 있는 화폐 구성이 없다는 의미이다.
const fs = require('fs');
let input = fs.readFileSync('../tc.txt').toString().trim().split('\n');
const [nm, ...arr] = input;
const [n, m] = nm.split(' ').map((v) => +v);
const coins = arr.map((v) => +v);
const d = [...Array(m + 1).fill(Infinity)];
const dp = (n, m, coins) => {
d[0] = 0;
for (const coin of coins) d[coin] = 1;
for (let i = 1; i <= m; i++) {
for (const coin of coins) {
if (i < coin) continue;
d[i] = Math.min(d[i], d[i - coin]) + 1;
}
}
return d[m];
};
function solution(n, m, coins) {
const result = dp(n, m, coins);
return result === Infinity ? -1 : result;
}
console.log(solution(n, m, coins));
반응형
'Algorithm > Javascript로 정리하는 이코테' 카테고리의 다른 글
[Javascript로 정리하는 이코테] 9. 그래프 이론 (2) | 2023.03.16 |
---|---|
[Javascript로 정리하는 이코테] 8. 최단 경로 (0) | 2023.03.15 |
[Javascript로 정리하는 이코테] 6. 이진 탐색 (0) | 2023.03.11 |
[Javascript로 정리하는 이코테] 5. 정렬 (0) | 2023.03.10 |
[Javascript로 정리하는 이코테] 4. DFS/BFS (0) | 2023.03.09 |