CS
[알고리즘] 다이나믹 프로그래밍(Dynamic Programming; DP)
shj718
2021. 10. 2. 12:11
다이나믹 프로그래밍이란?
▷다이나믹 프로그래밍은 주어진 문제를 더 작은 문제로 분할해서 가장 작은 문제의 답부터 구한 후 저장해놓고, 필요하면 꺼내쓰는 알고리즘이다. 따라서 답을 저장하기 위한 배열을 구축해야한다.
다이나믹 프로그래밍의 유형 2가지
① Top-down 방식
재귀함수를 활용하여 큰 문제를 해결하기 위해 작은문제를 호출한다.
다만, "메모이제이션" 기법을 활용하여 중복연산은 하지 않는다.
여기서 "메모이제이션"은 계산한 값을 리스트에 메모함으로서 중복된 연산을 하지 않고 바로 값에 접근하는 방식이다.
② Bottom-up 방식
반복문을 활용하여 점화식을 통해 작은문제부터 해결하여 큰문제를 해결한다.
다이나믹 프로그래밍에 주로 사용되는 방식이다. 왜냐하면 점화식이 곧 반복문의 식이 되기 때문이다.
어떤 문제에 사용할 수 있을까?
▷"어떤 문제의 최적해가 그 문제를 분할한 작은 문제의 최적해를 항상 포함한다."는 Principle of optimality(최적의 원칙)가 성립해야 한다.
EX) '최단 경로 문제' → vi에서 vj로의 경로가 최적이면 하위 경로 vi에서 vk로, vk에서 vj로도 최적이어야 함.
다이나믹 프로그래밍 사용절차
① 문제의 해답을 계산하는 점화식을 세운다.
② 가장 작은 사례부터 시작해서 전체 문제에 대한 해답을 구한다.
대표적인 문제
▷피보나치 수열
int d[50];
int fibonacci(int n) {
if(n==1) return 1;
if(n==2) return 1;
if(d[n]!=0) return d[n]; // 이미 한 계산은 저장해두었기 때문에 다시 안하는게 핵심!
return d[n] = fibonacci(n-1) + fibonacci(n-2);
}