[자료구조] Dynamic Programming 동적 계획법

Dynamic Programming/ Dp/ 동적 계획법 :

복잡한 문제를 단순한 작은 문제들로 나누고 반복적인 계산을 통해 최적해를 찾는 방법.

​

* 아래와 같은 키워드 사용

1. 분할과 정복 Divide and Conquer

2. 재사용 Reuse - '함수의 재사용, 메모이제이션 통한 계산 결과 재사용 등등' 에서의 재사용을 의미하는 듯.

3. 효율성 - 공간적 Memory Intensive

4. 효율성 - 시간적 Speedy

​

*메모이제이션 Memoization : 결과값을 저장하여 이후 계산에 계속 사용하는 것. 중복 계산이 없도록 함.

(피보나치 계산 시 계속 첫 값부터 재귀 시키는 것은 단순한 재귀, 시간도 오래 걸리며 효율이 떨어진다.

배열 잡아주고 결과값을 계속 저장하며 필요시에 불러오는 메모이제이션을 사용하게 되면 fib(10)을 구한다 했을 때도 배열의 fib(9) 값과 fib(8)

값만 불러와서 계산해주면 되는 것.)

​

방법 두 가지 :

1. Top Down - 가장 큰 문제를 해결하고 작은 문제들을 해결하는 방식, 재귀와 메모이제이션 사용

2. Bottom Up - 작은 문제를 해결하면서 큰 문제로 나아가는 방식, 반복문을 사용