다이나믹 프로그래밍(Dynamic Programming) : 동적 계획법

DP란?

: 답을 재활용해서 다시 사용해 비효율적인 계산을 줄인다.

한 번의 계산을 통해 답을 구한다.

현재의 답을 구하기 위해서 전에 구해놨던 답을 이용해서 구한다. 

 

피보나치 수열이 대표적인 예

 

2가지 방법이 있다.

 

1. Top-down

위에서 아래로 내려오는 것, 큰 문제를 작은 문제로 나누어 푸는 것이다.

피보나치 수열을 예로 들어 설명하자면 

네 번째 피보나치 수열을 구하기 위해서는 두 번째 피보나치 수열과 세 번째 피보나치 수열이 필요하다.

또 세 번째 피보나치 수열을 구하기 위해서는 첫 번째 피보나치 수열과 두 번째 피보나치 수열이 필요하다. 

이렇게 큰 문제를 작은 문제로 나눌 수 있다. 

 

2. Bottom-up

아래에서 위로 올라가는 것, 작은 문제부터 시작해 점점 큰 문제를 풀어나가는 것이다.

첫 번째 피보나치 수열을 구하고 두 번째 피보나치 수열을 구하면 세 번째 피보나치 수열을 구할 수 있다.