동적계획법(Dynamic programing, DP)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말하며 DP를 사용할 수 있는 조건은 아래 두가지와 같다.
- 최적 부분 구조(optimal substructure)
-큰 문제를 작은 문제로 나눌 수 있으며 작은문제들의 답을 모아서 큰문제를 해결할 수 있다. - 중복되는 부분 문제(overlapping subproblem)
-동일한 작은 문제를 반복해서 해결해야 한다.
DP를 사용하는 대표적인 예시인 피보나치 수열을 이용해보자.
점화식 : f(0)=1, f(1)=1, f(n)=f(n-1)+f(n-2)
n번째의 값을 구하는 코드는 아래와 같이 작성할 수 있다.
int fib(n)
{
if(n<=1) return 1;
else return fib(n-1)+fib(n-2);
}
위의 코드를 이용하여 6번째 수를 구하려면 사진과 같이 동일한 연산을 여러번 반복해서 수행하게 되어 n이 커질수록 연산횟수가 기하급수적으로 증가하게 된다.
메모이제이션 (Memoization) : DP를 구현하는 방법 중 하나로서, 한 번 계산한 결과를 메모리 공간에 메모해두는 기법으로 동일한 문제를 호출하면 저장했던 결과를 가져와서 해결한다.
시뮬레이션에서 재귀와 DP를 활용한 방식의 차이를 보면 DP를 사용했을때 연산이 훨씬 적은것을 확인할 수 있다.
DP의 구현 방법에는 Top Down, Bottom up 두가지 방식이 존재한다.
Bottom up
Bottom up 방식은 작은 부분 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식으로 반복문을 사용하여 반복적으로 부분 문제들을 해결하고, 결과를 배열 등에 저장한다.
Top Down
큰 문제를 작은 부분 문제로 나누어 해결하는 방식으로 재귀 함수를 사용하여 문제를 작은 부분 문제들로 나누고, 반복되는 문제해결을 피하기 위해 이전에 계산한 값을 저장하는 Memoization방식을 이용한다.
참고자료
https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming
위키백과
