Dynamic Programming (동적계획법)

DP  ?

 

" 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 "

 

이런 문제에 활용해요 !

 

• 큰 문제를 작은 문제로 나눌 수 있다
• 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다

최적성의 원리를 만족하는지 판단

 

최석성의 원리란 ?

주어진 문제의 부분해가 전체 문제의 해를 구하는데 사용되는지를 의미한다

---

피보나치 수열로 이해하기

소문제가 상위문제를 해결하기 위해 사용되는 대표적인 예시

DP 의 가장 좋은 예시인 피보나치 수열이 있다

F(n) 을 구할 때 트리를 보면 f(n-3) 연산식이 여러 번 사용되는데

상위 문제인 F(n) 을 구하기 위해서 여러 소문제들이 사용된다는 것을 알 수 있다

 

자주 사용되는 소문제들이 존재할 경우 자원의 낭비를 막기위해

" 동적프로그래밍에서는 소문제의 해를 저장" 해두고 사용하게 된다 !

---

중복 연산을 방지하기 위한 방법 (1) Memoization

첫번째 하향식 방식 Memoization 이다

단어 그대로 메모 해두었다가 호출이 있을 때 그대로 불러오는 것으로

연산을 두 번 이상 할 필요가 없어 시간이 줄어들게 된다

---

중복 연산을 방지하기 위한 방법 (2) Tabulation

두번째 상향식 방식 Tabulation 이다

작은 문제부터 하나하나 채워간다는 의미로

작은 문제의 정답을 이용해서 큰 문제의 정답을 풀어나가는 방법이다

---

다이나믹 프로그래밍 VS 분할정복

•분할 정복 (Divide and conquer)이란 ?

 하나의 문제를 여러 개의 부분 문제로 나누어 해결하는 방식

 

다이나믹 프로그래밍과 분할 정복의 차이점 " 부분 문제의 중복 "

다이나믹 프로그래밍은 각 부분 문제들이 서로 영향을 미치며 중복되지만

하지만, 분할 정복은 동일한 부분문제가 반복적으로 계산되진 않는다는 점이 차이점이다 !