[Algorithm] Dynamic Programming (동적 계획법)

Dynamic Programming

📢 분할 정복과 같은 접근 방식을 보이지만, 계산 결과를 재활용 하는 특징을 가진 알고리즘

---

🔎 Dynamic Programming 의미

• 분할 정복과 동일하게 작은 문제로 나누는 과정을 가져요.
• 동적 계획법에서 특정 부분 문제는 2번 이상 문제를 푸는 과정을 가질 수 있기 때문에 값을 저장해 놓음으로서 더 빠르게 문제를 해결할 수 있어요.
• 흔히들 DP이라고 줄여서 말해요.

---

📜 Dynamic Programming 조건

이를 적용해서 문제를 풀기 위해서는 아래 2가지 조건을 만족해야해요.

• Overlapping Subproblems (중복되는 부분 문제)
• Optimal Substructure (최적 부분 구조)

📂 Overlapping Subproblems (중복되는 부분 문제)

📢 2번 이상 호출되는 부분 문제

위의 의미에서 설명했듯이, 특정 부분 문제는 2번 이상 문제를 푸는 과정 을 가질 수 있어요. 이를 Overlapping Subproblems라고 말해요. Overlapping Subproblems는 불필요한 시간 낭비로 이어지기 때문에, Dynamic Programming을 통해 해결할 수 있어요.

📂 Optimal Substructure (최적 부분 구조)

📢 각 부분 문제의 최적해만 있다면 전체 문제의 최적해를 쉽게 얻어낼 수 있다

예를 들어 위의 그림에서 울산에서 대구까지 가는 가장 짧은 길을 찾는 문제를 풀려고 해요. 이때, 반드시 경주를 거쳐서 가야한다고 하면, 우리는 (울산 -> 경주) (경주 -> 대구) 각각의 가장 짧은 경로를 찾아 이를 연결하기만 한다면 (울산 -> 대구) 전체 경로에서 가장 짧은 경로를 찾을 수 있게 돼요.

---

📜 Dynamic Programming 종류

대개 2가지의 구현 방법이 있다고 알려져 있어요.

• Top-Down 방법
• Bottom-Up 방법

📂 Top-Down 방법

📢 작을 문제를 호출해서 큰 문제를 해결하는 방법

• 재귀 호출을 이용해서 문제를 해결하는 방법
• Memoization(메모이제이션)을 활용

📋 코드

// memo는 -1로 초기화가 되어있다는 가정
int fibonacchi(int num, vector<int> memo) {
  // memo[num]이 -1이라는 것은 처음 부분 문제를 해결한다는 의미
  if(memo[num] == -1) {
    int result;
    if(num == 0 || num == 1)
      result = n;
    else
      // 함수의 재귀 호출을 사용
      result = fibonacchi(n - 1, memo) + fibonacchi(n - 2, memo);
    memo[n] = result;
  }
  // -1이 아니라는 것은 이미 문제를 한 번 풀었다는 의미이므로 memeo 값 사용
  return memo[n];
}

📂 Bottom-Up 방법

📢 작은 문제부터 하나씩 해결해 큰 문제를 해결하는 방법

• 반복문을 이용하여 문제를 해결하는 방법
• Table을 활용

📋 코드

int fibonacchi(int num) {
  // table을 미리 선언
  vector<int> table(num + 1, 0);
  table[0] = 0, table[1] = 1;
  for(int i = 2; i <= n; i++)
    // table 값을 이용하여 해결
    // 가장 작은 문제를 해결하면서 큰 문제를 해결해나간다
    table[i] = table[i - 1] + table[i - 2];
  return table[n];
}

---

📋 예제

백준 2839 - 설탕 배달

백준 2839 - 해답

백준 9251 - LCS

백준 9251 - 해답