04)Dynamic Programming[동적계획법]

▣ Dynamic-Programming(동적계획법)

: 동적계획법이랑 복잡한 문제를 여러 sub-problem으로 나누어 해결하는 방법이다.

        ->어떻게? 해당 sub-problem의 solution들을 Table(여분의 저장공간을 필요하게 된다.)에 기록 함으로써 중복계산을 피하는 방법.

장점: 중복계산을 피하기 때문에 시간적 이점을 얻을 수 있습니다.

단점: 추가적인 메모리공간을 필요로 합니다.

       (시간과 메모리의 trade-off)

example) 피보나치 함수의 계산

피보나치 함수는 Fib(n) = Fib(n-1)+Fib(n-2)(Fib(0)=1, Fib(1)=1)로 정의 할 수 있습니다.

원하고자 하는 피보나치 값을 계산하기 위해서는 위 그림과같은 과정을 수행하게 되며, 보다시피 여러번의 중복계산이 되어지는 것을 볼 수 있습니다. 

이때의 중복되는 결과값을 미리 준비된 테이블에 저장함으로써 중복계산을 피할 수 있으며, 테이블에 기록하는 방법을 Memoization기법이라고 표현합니다.

이때의 방법은 Top-down 방법과 Buttom-Up 방법이 존재 합니다. 

1. Top-Down 방법

  : 큰 문제로 부터 재귀적으로 들어가 문제를 Sub-problem으로 나눈뒤 return 값을 Table에 저장해 나가는 방식입니다.

   -> 만약 해당 위치에서의 table이 채워져 있다면 더 안으로 들어가지 않고 그 값을 불러오게 됩니다.

2. Buttom-Up 방법

  : 이미 작은 문제로부터 큰문제를 풀어나가는 방식입니다.

Fib(n)을 구하기 위해서는 Fib(n-1)과 Fib(n-2)를 알아야 하므로 Fib(n-1)과 Fib(n-2)를 미리 구하여 원하는 값을 얻는 방식입니다.

그림에서 보다시피 이미 fib(0)과 fib(1)은 처음 초기화과정을 통해 Table에 채워져 있습니다.

그리고 그 후 과정은 함수 식을 만족시켜나가며 값을 채워나가 주면 되는 것입니다.