[Algorithm] 다이나믹 프로그래밍

다이나믹 프로그래밍

: 큰 문제와 작은 문제를 나눠서 해결하는 기법

1. Overlapping Subproblem

- 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다

- 문제를 작은 문제로 쪼갤 수 있다

2. Optimal Substructure

- 문제의 정답을 작은 문제의 정답에서 구할 수 있다

- 메모를 한다고 해서 "Memoization"

Tob-down

1. 문제를 풀어야한다

2. 문제를 작은 문제로 나눈다

3. 작은 문제를 푼다

4. 작은 문제를 풀었으니, 이제 문제를 푼다

# 재귀 함수로 구현

# 시간복잡도 : 채워야하는 칸의 수(memo 배열) X 1칸을 채우는 시간복잡도

Bottom-up

1. 문제를 크기가 작은 문제부터 차례대로 푼다

2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다

3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다

4. 그러다보면, 언젠간 풀어야하는 문제를 풀 수 있다

# 반복문을 이용해 구현

#include <iostream>
 
using namespace std;
 
int fibonacci(int n);
 
int main(int argc, const char * argv[]) {
    int t;
    cin >> t;
    
    cout << fibonacci(t) << endl;
}
 
int d[100];
int fibonacci(int n){
    if(n<=1){
        return n;
    }else{
        if(d[n]>0){
            return d[n];
        }
        d[n] = fibonacci(n-1) + fibonacci(n-2);
        return d[n];
    }
}

다이나믹 문제 풀이 전략

- 문제에서 구하려고 하는 답을 문장으로 나타낸다

- 예 : 피보나치 수를 구하는 문제

- N번째 피보나치 수

- 이제 그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다

- Top-down인 경우에는 재귀 호출의 인자 개수

- 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현

📝1463번 문제 (1로 만들기)

📝11726번 문제 (2xn 타일링)