Dynamic Programming

동적 계획법

- 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다.

작은 문제들을 해결한 뒤, 해당 답을 저장해놓고 그보다 큰 문제를 풀이하는데 앞서 저장해둔 값들을 활용해 풀어나간다.

 

DP(Dynamic Programming)을 사용 조건

1. 작은 문제로 쪼갤 수 있다.

2. 작은 문제에서 구한 값은 큰 문제를 풀이할 때도 동일한 값이여야 한다.

이때, 메모이제이션(Memoization)이 활용된다.

 

+Memoization : 계산한 값을 메모리에 저장해두고, 여러번 같은 값 계산을 피하는 최적화 기법(실행속도를 높이고, 메모리를 절약할 수 있다.)

 

---

EX) Fibonacci수열

피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21 ... 의 수열이다.

즉, fibo(3) = fibo(2) + fibo(1)

fibo(n) = fibo(n-1) + fibo(n-2) 이다.

 

또한, fibo(n)을 구하기 위해 fibo(1)부터 fibo(n-1) 까지의 작은 문제들이 반복되며, 항상 작은 문제들의 값은 같다.

#include <stdio.h>
//배열사용시, index주의
int arr[100];

int fibo(int n){
    if(n<2)
    	return arr[n];
//메모이제이션
    if(arr[n]!=0)
    	return arr[n];
    arr[n] = fibo(n-1) + fibo(n-2);
    return arr[n];
}

int main(){
//초기 값 명시
    arr[1] = 1;
    arr[2] = 1;
    printf("%d\n", fibo(10));
}

여기서의 점화식은 arr[] = fibo(n-1) + fibo(n-2);

DP의 경우에는 보통 규칙성을 찾아 점화식을 세워 해결한다.

 

---

Bottom-up과 Top-down

Bottom-up은 작은 문제부터 하나씩 구해가며, 큰 문제를 해결하는 방법이다.(반복문을 이용한 fibo등)

Top-down은 보통 재귀함수로 구현되는 경우이며, 큰 문제해결시 작은 문제가 풀리지않았다면, 작은 그때 작은 문제를 해결한다.

 

분할정복과의 차이점 : DP의 경우 작은 문제의 답이 항상 같아야한다.