알고리즘: 동적 계획법(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