[알고리즘] 다이나믹 프로그래밍 DP

다이나믹 프로그래밍

기억하기 프로그래밍 이라고 생각하면 쉽다.

큰 문제를 작은 문제로 나누어 푸는 문제.

 

 

분할 정복과 비슷하지 않나? 

-> 비슷하지만 차이가 하나 있는데, 그것은 "작은 문제가 중복이 일어나는지 안일어나는지" 이다.

분할정복 : 큰 문제를 해결하는게 어려워 단지 작은 문제로 나누어 푸는 방법.

DP : 작은 문제들이 반복되는 것 (답이 바뀌지 않음) 을 이용해 풀어 나가는 방법 

 

푸는 방법?

모든 작은 문제들은 한번만 풀어야 한다.

그래서 정답을 구한 작은 문제를 어디엔가 메모 해 놓는다. (Memoization)

그래서 보다 큰 문제를 풀어나갈 때 앞서 똑같은 작은 문제가 나타날 때 메모한 작은 문제의 결과값을 이용

 

사용 조건?

1. 작은 문제가 반복이 일어나는 경우

2. 같은 무제는 구할 때 마다 정답이 같음

 

Ex

피보나치

 

 

 

 

Reference

https://galid1.tistory.com/507