동적계획법이란 무엇인가?

1. 동적계획법?

 

다이나믹 프로그래밍(dynamic programming)

 

‘하나의 문제는 단 1번만 풀도록 하는 알고리즘’

 

2개의 가정 하에 사용할 수 있다

 

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

 

1-2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤에 각각을 처리한 다음 나중에 전체의 답을 구하는 것

 

이 과정에서 이미 계산한 결과는 배열에 따로 저장한다음 나중에 동일한 계산을 할때 저장된 값을 단순히 호출하여 반환하기만 하면 된다

 

 

2. 피보나치 수열

 

피보나치 수열의 점화식은 $$a_{n}=a_{n-1}+a_{n-2}$$

 

특정한 위치의 숫자를 구하기 위해 바로 이전의 숫자와 두번 이전의 숫자의 합을 구함

 

초기값에 따라 전체 수열이 달라짐

 

예를 들어 $a_{1}=1, a_{2}=1$라고 한다면 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,... 와 같이 구해짐

 

만약 단순하게 피보나치 수열의 일반항을 구하기 위해서 $a_{15}$를 구해본다고 가정해보면

 

$a_{14}$와 $a_{13}$을 알아야하고 $a_{14}$를 알기 위해 $a_{13}$과 $a_{12}$를 알아야한다

 

그림1. 피보나치 수열 문제 해결 알고리즘

 

이런 경우 단순히 계산한다면 이미 해결한 문제를 다시 반복적으로 해결하므로 상당히 비효율적

 

그림만 보더라도 $a_{12}$를 3번이나 반복적으로 다시 계산해야한다는 점이 비효율적이다

 

$a_{50}$만 하더라도 계산량이 2의 50제곱정도로 계산이 불가능할 정도

 

 

3. 참고

 

https://blog.naver.com/ndb796/221233570962

20. 다이나믹 프로그래밍(Dynamic Programming)