다이나믹 프로그래밍 2 (이론 정리)

Dynamic Programming(DP)는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제 해결 패러다임이다.

 

DP는 왜 사용할까?

일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 발생한다.
그럼 한 번 구한 작은 문제의 결과 값은 저장해두고 재사용하자! 가 DP의 사용 이유이다.

 

분할 정복과 무엇이 다를까?

작은 문제가 중복이 일어나는지, 안일어나는지에 따라 차이가 있다.

분할 정복은 큰 문제를 해결하기 어려워 단지 작은 문제로 나누어 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나지 않는다.

동적 프로그래밍은 작은 부분 문제들이 반복이된다.

 

Memoization?

한번 계산한 작은 문제를 저장해놓고 다시 사용을 하는 방식을 말한다.

 

Bottom-up과 Top-down

1) Bottom- up은 작은 문제부터 차근차근 구해나아가는 방법이다.

2)Top- down은 재귀함수로 구현하는 대부분의 경우이다.

➡️ Top-down은 소스의 가독성이 증가되는 장점이 있지만, 작성하기에 난이도가 높다. Bottom-up의 경우 풀기는 쉽지만 가독성이 저하되기도 한다.