DP: Dynamic Programming 이란?

"동적 계획법"

 

- 알고리즘 설계 기법 및 최적화 이론의 한 기술

- 답을 재활용한다

   - 하나의 큰 문제를 작은 문제로 나누어 해결한다

   - 즉, 큰 문제를 풀기 위해 그 문제를 작은 문제로 나누고, 작은 문제를 푼 해법을 활용해서 큰 문제를 푼다

 

왜 Dynamic Programming인가?

   - Dynamic이란 단어가 멋있어서! (진짜임)

 

왜 DP가 중요한가?

- 적절한 문제에 DP를 사용하면 매우 빠르게 답을 얻을 수 있다

- 하지만 '적절한' 문제를 어떻게 판단하는가가 문제이다

 

DP의 사용 조건

1. Opitmal Substructure (최적 부분 구조)

   - Combining the optimal results of subproblems should lead to the optimal result of the bigger problem

   - 소문제들의 최적 결과 값을 이용해 전체 문제의 최적의 결과를 낼 수 있어야한다

2. Overlapping Subproblems (겹치는 소문제)

   - Same subproblems are solved repeatedly in different parts of the problem

   - 작은 문제의 결과를 "재사용"해서 원하는 결과를 도출할 수 있어야한다

 

예시:

A에서 C로 가고 싶은 경우, (1) A => B로 가는 경로, (2) B => C로 가는 경로로 문제를 나눠 각각 해결 후 더하면 A => C로 가는 경로가 완성 된다!

 

하지만 

이러한 경우엔 A => C로 가는 경로가 있기때문에 이전처럼 A-B, B-C로 나눠도 최적의 경로가 나오지 않는다. 즉, "최적 부분 구조"의 조건에 맞지 않는 경우이다.

 

 

DP로 문제 푸는 방법

- 방식:

   1. 메모하기: 변수 값에 따른 결과를 저장할 배열을 미리 만들고, 그 결과가 나올때마다 배열에 저장 후, 저장된 값을 재사용하는 방식

   2. 변수 간 관계식 만들기:  예시 - Fibonacci Sequence의 f(n) = f(n-1) + f(n-2)

 

- 두가지 방식:

   1. Top-Down Approach (Memoization)

      - 큰 문제를 작은 부분 문제로 나누며 해결하는 방식

      - 재귀 함수 (Recursion)을 사용하여 문제를 쪼게고, 중복 계산을 피하기 위해 이전에 계산한 값을 Memoize 한다

      - We start with the final solution and recursively break it down into smaller problems, sotre the results of the solved subproblems in a Memoization table

      - Suitable when there number of subproblems is large and many of them are reused

 

   2. Bottom-up Approach (Tabulation)

      - 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식

      - 반복문을 사용하여 반복적으로 부분 문제들을 해결하며, 결과를 배열에 저장하는 방식

      - We start with the smallest subproblem and gradually build up to the final solution.

      - We store the results of solved subproblems in a table to avoid redundant calculations

 

 

DP를 자주 사용하는 알고리즘

1. Longest Common Subsequence (LCS): 

2. Shortest Path Problem: 

3. Knapsack Problem: 

4. Fibonacci Sequence:

 

 

예시 (출처)

1. Longest Increasing Subsequence (LCS): Bottom-Up

function longestIncreasingSubsequence(nums) {
  const n = nums.length;

  // 🌟 메모이제이션 🌟
  // 동적 계획법을 위한 배열 초기화
  const dp = new Array(n).fill(1);

  // 🌟 점화식 🌟
  // 최장 증가 부분 수열 계산
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  // 결과 중 최대값 반환
  return Math.max(...dp);
}

// 예시로 배열 [10, 9, 2, 5, 3, 7, 101, 18]의 최장 증가 부분 수열의 길이 출력
const nums = [10, 9, 2, 5, 3, 7, 101, 18];

console.log(longestIncreasingSubsequence(nums));  // Output: 4

 

2. Shortest Path Problem: Bottom-Up

function shortestPath(graph, start, end) {
  const n = graph.length;
  // 🌟 메모이제이션 🌟
  const dp = new Array(n).fill(Infinity);
  dp[start] = 0;

  // 🌟 점화식 🌟
  for (let i = start; i <= end; i++) {
    for (let j = 0; j < n; j++) {
      if (graph[i][j] !== 0 && dp[i] + graph[i][j] < dp[j]) {
        dp[j] = dp[i] + graph[i][j];
      }
    }
  }

  return dp[end];
}

// 예시로 그래프와 시작점, 도착점이 주어졌을 때 최단 경로의 길이 출력
const graph = [
  [0, 4, 2, 0],
  [4, 0, 1, 5],
  [2, 1, 0, 8],
  [0, 5, 8, 0]
];
const start = 0;
const end = 3;

console.log(shortestPath(graph, start, end));  // Output: 6

 

3. Knapsack Problem: Bottom-Up

function knapsack(weights, values, capacity) {
  const n = weights.length;

  // 🌟 메모이제이션 🌟
  // 동적 계획법을 위한 2차원 배열 초기화
  const dp = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    dp[i] = new Array(capacity + 1).fill(0);
  }

  // 🌟 점화식 🌟
  // 배낭 문제 해결
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= capacity; j++) {
      if (weights[i - 1] > j) {
        // 현재 아이템을 배낭에 넣을 수 없는 경우
        dp[i][j] = dp[i - 1][j];
      } else {
        // 현재 아이템을 배낭에 넣을 수 있는 경우
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
      }
    }
  }

  // 결과 반환
  return dp[n][capacity];
}

// 예시로 아이템의 무게와 가치, 배낭의 용량이 주어졌을 때 최대 가치 출력
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 7;

console.log(knapsack(weights, values, capacity));  // Output: 9

 

 

4. Fibonacci Problem: Top-down 

function fibonacci(n) {
  // 🌟 메모이제이션 🌟
  // 피보나치 수열을 저장할 배열
  const dp = new Array(n + 1);

  // 초기값 설정
  dp[0] = 0;
  dp[1] = 1;

  // 🌟 점화식 🌟
  // 피보나치 수열 계산
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }

  // 결과 반환
  return dp[n];
}

// 예시로 n = 10일 때 피보나치 수열 값 출력
console.log(fibonacci(10));  // Output: 55