[Algorithm Tech] Dynamic Programming(동적 계획법)

* Dynamic Programming(동적 계획법)

큰 문제를 작은 문제로 나눠서 푸는 알고리즘

큰 문제를 작은 문제로 나누는 방식은 Divide and Conquer(분할 정복) 방식과 비슷하지만 차이점이 있다.

분할 정복의 경우 결과가 한번만 사용되고, 분할하여 작은 문제를 푸는 것이 성능을 향상시키지만,

동적 계획법의 경우 결과가 여러번 사용되고, 결과를 재사용하여 성능을 향상시킨다.

DP의 핵심은 점화식을 어떻게 세우는지와 DP에 어떤 값을 메모이제이션 할 것인지를 정하는 것이다.

메모이제이션이란 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법이다.

* Dynamic Programing 문제를 푸는 방법

- Top-Down (재귀 사용)

큰 문제를 작은 문제로 나누어 결과값을 가지고 큰 문제를 푼다.

메모이제이션 작업을 필수로 진행해야 한다.

- Bottom-Up (For문 사용)

작은 문제를 풀어 결과값을 가지고 큰 문제를 푼다.

Dynamic Programing은 피보나치가 대표적인 예로 사용된다.

백준 1003 :: 피보나치 함수