[개념] 다이나믹 프로그래밍(동적계획법)

연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘

다이나믹 프로그래밍 사용할 수 있는 경우

1. 큰 문제를 작은 문제로 나눌 수 있다
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

---

메모이제이션 (캐싱)

• 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
• 한 번 구한 정보를 리스트에 저장하는 것

탑다운(Top-Down) / 보텀업(Bottom-Up) 방식

탑 다운 방식 (메모이제이션)

• 하향식
• 재귀 함수를 이용해 다이나믹 프로그래밍 소스코드를 작성하는 방법
• 큰 문제를 해결하기 위해 작은 문제를 호출 하는 방법

보텀업 방식 (DP)

• 다이나믹 프로그래밍의 전형적인 형태
• 상향식
• 단순히 반복문을 이용해 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출하는 방법

---

대표 문제 : 피보나치 수열

#include <iostream>
#include <stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;

int fibo(int x) {
    if (x == 0 || x == 1) {
        return 1;
    }
    return fibo(x - 1) + fibo(x - 2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int num[6];
    memset(num,sizeof(num), 0);

    cout<<fibo(5);
}