[알고리즘] 동적 계획법(Dynamic Programming)

🟡 동적 계획법(Dynamic Programming)

- 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

 

 

🟡 동적 계획법의 핵심 이론

① 큰 문제를 작은 문제로 나눌 수 있어야 한다.

② 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.

③ 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모이제이션(memoization) 기법이라고 한다.

④ 동적 계획법은 톱-다운(top-down)방식과 바텀-업(bottom-up) 방식으로 구현할 수 있다.

 

· 톱-다운 방식: 위에서부터 문제를 파악해 내려오는 방식. 주로 재귀함수로 코드를 구현

· 바텁-업 방식: 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식. 주로 반복문의 형태로 구현

 

🟡 동적 계획법의 가장 대표적인 문제 - 피보나치 수열

- 피보나치 수열 공식

D[N] = D[N-1] + D[N-2]