[백준] DP , 백준 2294

오늘은 DP(Dynamic Programming)에 대해 알아보겠습니다.

⭐️ DP란 ?

Dynamic Programming이라고 돼있어서 무언가 동적으로 풀이하는 알고리즘이라고 생각할 수 있지만 , 이름에 큰 뜻은 없습니다. (멋있어서 지었다고 알고리즘 만든 사람이 밝힘) DP는 문제를 더 작은 부분 문제로 나누어 해결하고 , 그 해답을 저장해둔 후 재활용하여 전체 문제를 해결하는 알고리즘 설계 기법입니다.

DP를 사용하기 위해서는 두 가지 조건이 필요합니다.

1. 큰 문제를 작은 문제로 나눌 수 있는지
2. 작은 문제에서 구한 해답이 전체로 일반화될 수 있는지

앞서 설명한 내용과 같죠 ?

해답을 저장해두는 방식에는 대표적으로 메모이제이션(Memoization)이 있습니다.

메모이제이션(Memoization)

메모이제이션은 이름 그대로 한 번 구한 결과를 다시 구하지 않기 위해 메모리에 결과를 저장해두는 것을 의미합니다. 보통 재귀 호출을 이용하여 사용됩니다.

const data = [0, 1];

function fibonacci(n) {
    // 0과 1
    if (n < data.length) {
        return data[n];
    }
    data[n] = fibonacci(n - 1) + fibonacci(n - 2);

    return data[n];
}

console.log(fibonacci(8));
console.log(data);
// [
//     0, 1,  1,  2, 3,
//     5, 8, 13, 21
//   ]
console.log(fibonacci(7));

메모이제이션이 된 배열을 보면 이전에 진행했던 값들이 메모리에 남아있는 것을 볼 수 있습니다. 찾고자 하는 값이 이전에 계산된 값이라면 데이터 배열에 직접 접근하면 되고 , 새로 구해야 한다면 이전 값들을 이용해서 구하면 되는 것을 볼 수 있습니다.

⭐️ 백준 2294 : 동전 2

function solution(input) {
    const [n, k] = input[0];
    const coins = [0, ...input.slice(1).map((el) => +el)].sort((a, b) => a - b);
    const dp = [0, ...Array(k).fill(100001)];

    for (let i = 1; i <= n; i++) {
        // 동전 가치 별로 최소 경우의 수 갱신
        const coin = coins[i];

        for (let j = 1; j <= k; j++) {
            // coin>j 의 경우는 동전을 사용할 수 없는 경우
            if (coin <= j) {
                // coin[i-1] 동전 가치로 만들 수 있는 경우의 수 (dp[j])와 ,
                // 현재 동전 가치를 뺐을 때 ex) coin[i]=12이고 , j는 14일 때 ,
                // dp[2] => 즉 , 2를 만들 수 있는 최소 경우의 수
                // 둘을 비교하여 최솟 값을 dp 배열에 넣는다.
                dp[j] = Math.min(dp[j - coin] + 1, dp[j]);
            }
        }
    }
    dp[k] !== 100001 ? console.log(dp[k]) : console.log(-1);
}

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});

const input = [];

rl.on("line", (line) => {
    input.push(line.split(" ").map(Number));
}).on("close", () => {
    solution(input);
    process.exit();
});