[알고리즘] 동적 계획법(Dynamic Programming)

개요

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결
• 메모이제이션(Memoization)을 이용
  • 이전에 계산한 값을 저장해두었다가 사용함으로서 중복 계산 방지
• 최적성의 원리(Principle of optimality를 만족시켜야 함
  • 주어진 문제에 대해 최적해가 분할된 부분 문제에 대한 최적해로 구성

방법

• 점화식을 만들어서 그대로 구현

예제

• 피보나치 수열
  • C++
    • 코드

       #include <ctime>
       #include <iostream>
              
       using namespace std;
              
       long long memoization[100000] = {0, 1};
              
       long long fibonacci(const int& n, const bool isDP = false) {
           if (n == 0) {
               return 0;
           } else if (n == 1) {
               return 1;
           }
              
           if (isDP && memoization[n] != 0) {
               return memoization[n];
           }
              
           return memoization[n] = fibonacci(n - 1, isDP) + fibonacci(n - 2, isDP);
       }
              
       int main() {
           time_t start = time(nullptr);
           cout << "result : " << fibonacci(45, true) << ", time : " << time(nullptr) - start
                << "\n";
              
           start = time(nullptr);
           cout << "result : " << fibonacci(45) << ", time : " << time(nullptr) - start << "\n";
           return 0;
       }
      

    • 결과

       result : 1134903170, time : 0
       result : 1134903170, time : 21