동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming)

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

1. vs 분할 정복 기법 (Devide and Conquer)

• 분할정복은 큰 문제 해결이 어려워, 작은 문제로 나누어 푸는 방법임.

  • 작은 문제에서 반복 X

• Ex) 피보나치 수열 : 특정 숫자 D[i]를 구하기 위해 , D[i-1] 값과 D[i-2] 값의 합을 구해야함

  • 병합정렬 시, 단순 분할 정복 기법을 사용하면 이미 해결한 문제를 반복하므로 비효율적

• 하나의 문제를 단 한 번만 풀도록 함

  • 모든 작은 문제들은 한 번만 풀어야 함. 큰 문제를 풀어나갈 때, 작은 문제가 나타나면 이전 작은 문제의 결과값 이용

2. 조건 (가정)

1) 큰 문제를 작은 문제로 나눌 수 있다

• 크고 어려운 문제 → 작게 나누어 해결 → 전체의 답

  • 분할정복과 다르게, '메모이제이션(Memoization)' 이 사용됨

    → 이미 계산한 결과는 배열에 저장

2) 작은 문제가 반복될 때 : 같은 문제는 구할 때 마다 결과가 같다

3. 분할정복 vs 동적계획 예시 - 피보나치

• 분할정복 : 계산을 할 때 마다 이전 원소를 다시 구해야함

#include <iostream>
using namespace std;

int fib(int n) {
    if(n == 1) return 1;
    if(n == 2) return 1;
    return d(n - 1) + d(n - 2);
}

int main() {
    cout<<fib(10);
    return 0;
}

• 동적계획법 (메모이제이션)

#include <iostream>
using namespace std;

int arr[100]; // 계산한 숫자 저장, 전역변수는 항상 0으로 초기화 되어있음

int fib(int n) {
    if(n == 1) return 1;
    if(n == 2) return 1;
    if(arr[n] != 0) return d[n]; // 이미 계산한 적이 있다면
    return arr[n] = fib(n - 1) + fib(n - 2);
}