TIL-2024.02.28 - 알고리즘 - 다이나믹 프로그래밍

 

------- 다이나믹 프로그래밍

- 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하는 방법

- 각 하위 문제의 해결책을 저장하고 재사용함으로써 전체 문제의 해결책을 효율적으로 찾아냅니다

- 일반적으로, Bottom Up이 더 시간 효율적

 

 

핵심 원리: 

1. 중복된 하위 문제(Overlapping Subproblems): 
   - 주어진 문제가 같은 작은 문제를 반복적으로 해결해야 할 때, 이를 중복된 하위 문제라 칭함
   - 이러한 문제의 해결책을 한 번만 계산하고, 결과를 저장한 후 필요할 때마다 재사용함으로써 계산 시간을 대폭 감소 
2. 최적 부분 구조(Optimal Substructure): 
   - 큰 문제의 최적 해결책이 그 문제의 하위 문제의 최적 해결책에서 파생될 수 있을 때, 이를 최적 부분 구조라 칭함
   - 즉, 전체 문제의 최적 해가 하위 문제의 최적 해들로부터 구성될 수 있다는 것입니다. (하위 최적의 해 => 전체 최적의 해)

 

구현 방법:

1. Top-Down (메모이제이션 사용): 
   - 재귀를 사용하여 큰 문제를 작은 문제로 나누고, 각 하위 문제의 결과를 저장(메모)하여 중복 계산을 방지. 
2. Bottom-Up (타뷸레이션 사용): 
   - 가장 작은 하위 문제부터 시작하여 차례대로 해결책을 구축해 나가며, 이를 통해 최종 문제의 해결책을 얻습니다. 이 방법은 일반적으로 반복문을 사용합니다.

 

예제: 피보나치 수열(Bottom-Up)

function fibonacci(n) {
  if (n <= 1) return n; // n이 0 또는 1인 경우, n을 그대로 반환

  let dp = [0, 1]; // 처음 두 피보나치 수를 초기화

  // 피보나치 수열을 Bottom-Up 방식으로 계산
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // 이전 두 피보나치 수의 합을 저장
  }

  return dp[n]; // n번째 피보나치 수 반환
}

console.log(fibonacci(10)); // 55

 

 

예제: 피보나치 수열(Top-Down)

// 계산된 피보나치 수열의 값을 저장하기 위해 사용. 이 배열은 함수 호출 간에 계산된 값을 저장하여, 같은 계산의 반복을 피하고 효율성을 높이는 데 사용됩니다.
let memo = [];

function fibonacci(n) {
  // memo 배열에서 n번째 피보나치 수가 이미 계산되어 저장되어 있는지 확인합니다. 
  // 만약 memo[n]이 undefined가 아니면(이미 계산된 값 존재), 그 값을 바로 반환하여 불필요한 계산을 줄입니다.
  if (memo[n] !== undefined) return memo[n];

  // 피보나치 수열에서 첫 번째와 두 번째 수는 각각 0과 1입니다. 따라서 n이 1 이하일 경우 n 자체가 피보나치 수입니다.
  if (n <= 1) return n;

  // 재귀 호출을 사용하여 n번째 피보나치 수 계산
  // n번째 피보나치 수를 계산하기 위해, (n-1)번째와 (n-2)번째 피보나치 수의 합을 재귀적으로 계산합니다. 
  // 이때 계산된 값을 memo[n]에 저장하여, 나중에 같은 값을 다시 계산할 필요가 없도록 합니다.
  memo[n] = fibonacci(n - 1) + fibonacci(n - 2);

  // 마지막으로, memo[n]에 저장된 n번째 피보나치 수를 반환합니다. 
  // 이 값은 이제 n번째 피보나치 수의 최종 계산 결과입니다.
  return memo[n];
}

console.log(fibonacci(10)); // 55

 

 

예제: 계단 오르기 문제 (Bottom-Up 접근)

function climbStairs(n) {
  if (n === 1) return 1; // 계단이 하나인 경우, 오르는 방법은 하나뿐입니다.
  
  // dp 배열을 초기화합니다. dp[i]는 i번째 계단에 도달하는 방법의 수입니다.
  let dp = new Array(n + 1);
  dp[1] = 1; // 1번째 계단에 도달하는 방법의 수는 1가지입니다.
  dp[2] = 2; // 2번째 계단에 도달하는 방법의 수는 2가지입니다 (1계단 + 1계단, 2계단).

  // 3번째 계단부터 n번째 계단까지 각 계단에 도달하는 방법의 수를 계산합니다.
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  return dp[n]; // n번째 계단에 도달하는 방법의 수를 반환합니다.
}

console.log(climbStairs(4)); // 출력: 5

 

 

예제: 최소한의 동전 교환 (Top Down)

 

function minCoins(coins, amount) {
  // 메모이제이션을 위한 배열을 초기화합니다. 금액 + 1의 크기를 가지며, 초기값은 무한대로 설정합니다.
  const memo = Array(amount + 1).fill(Infinity);
  memo[0] = 0; // 0원을 만드는 데 필요한 동전 개수는 0개입니다.

  function dp(n) {
    // 이미 계산된 경우, 저장된 값을 반환합니다.
    if (memo[n] !== Infinity) return memo[n];

    // 모든 동전에 대해 반복합니다.
    for (let coin of coins) {
      if (n - coin >= 0) {
        memo[n] = Math.min(memo[n], dp(n - coin) + 1);
      }
    }

    return memo[n];
  }

  // dp 함수를 호출하여 결과를 계산합니다.
  const result = dp(amount);

  // 결과값이 Infinity라면, 주어진 금액을 만들 수 있는 조합이 없는 것입니다.
  return result === Infinity ? -1 : result;
}

// 예시: 동전 [1, 2, 5], 목표 금액 11
console.log(minCoins([1, 2, 5], 11)); // 출력: 3 (5+5+1)

 

 

 

예제: 최소한의 동전 교환 (Bottom Up)

function minCoins(coins, amount) {
  // 각 금액에 대한 최소 동전 개수를 저장할 배열을 초기화합니다.
  // 배열의 크기는 amount + 1이며, 모든 값을 무한대로 초기화합니다.
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0; // 0원을 만드는 데 필요한 동전 개수는 0개입니다.

  // 1원부터 주어진 금액까지 각 금액에 대해 최소 동전 개수를 계산합니다.
  for (let i = 1; i <= amount; i++) {
    // 사용 가능한 모든 동전에 대해 반복합니다.
    for (let coin of coins) {
      // 현재 금액에서 동전의 값을 뺀 금액이 0보다 크거나 같은 경우에만 계산을 진행합니다.
      if (i - coin >= 0) {
        // 현재 금액을 만드는 데 필요한 최소 동전 개수를 업데이트합니다.
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  // 주어진 금액을 만드는 데 필요한 최소 동전 개수를 반환합니다.
  // 만약 주어진 금액을 만들 수 없다면 -1을 반환합니다.
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// 예시: 동전 [1, 2, 5], 목표 금액 11
console.log(minCoins([1, 2, 5], 11)); // 출력: 3 (5+5+1)