다이나믹 프로그래밍

정의

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

1. DP (Dynamic programming) -> 중복 발생 가능
2. 분할정복 (divide & conquer) -> 중복 발생x -> 두 가지 모두 큰 문제를 작은 문제 여러가지로 나누는 알고리즘

---

두 가지 속성을 만족해야 다이나믹 프로그래밍으로 풀수있다.

1. overlapping subproblem 겹치는 작은 부분문제들이 중복이되는 경우.

2. Optimal Substructure (최적부분구조) 문제의 정답이 작은문제의 정답을 통해 구할 수 있는경우.

---

Overlapping subproblem

• 피보나치 수

큰 문제와 작은 문제는 상대적

1-1)문제: N번째 피보나치 수를 구하는 문제 1-2)작은 문제: N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

2-1)문제: N-1번째 피보나치 수를 구하는 문제 2-2)작은 문제: N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

3-1)문제: N-2번째 피보나치 수를 구하는 문제 3-2)작은 문제: N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

-> 작은 문제들이 중복된다. -> 큰 문제와 작은 문제를 같은방법 으로 풀수있음.

---

Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할수있음

  Top-down 방식

  큰문제부터 쪼개가면서 작은문제를 만들고 합쳐가면서 원래문제를 푼다. (재귀)

---

Bottom-up 방식

작은문제를 모아서 큰문제만들고 다시 작은문제를 모아서 큰문제를 만들고 (반복문)

---

Top-down VS Bottom-up 시간 차이

-> 알수 없음

• 어떤 경우에는 Top-down이 어떤 경우에는 Bottom-up이 빠를수도 있다.

• 스택오버플로우 발생가능성
• 또한 예를들어, Fn = Fn-10 + Fn-20 이라는 점화식이 있다고하면 Top-down은 몇번만 풀어주면되는데 down-Top은 1,2,3,4,5 … 쭉 처음부터 풀어야하기 때문이다.
• 일단 맘에드는거 하나 쓰자. 물론 나중가면 두가지 방식 중 하나로만 풀수있는 문제가 있긴하다.