동적 계획법(Dynamic Programming)

• 탐욕 알고리즘과 함께 언급되는 알고리즘
• 공통점 : 작은 문제에서 출발
• 차이점
  • 탐욕 알고리즘 : 매 순간 최적의 선택을 찾는 방식
  • 동적 계획법 : 모든 경우의 수를 조합해 최적의 해법을 찾는 방식

주어진 문제를 여러 개의 작은 문제로 나누어 풀고,

하위 문제들의 해결 방법을 결합하여 최종 문제를 해결한다.

하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다.
→ 하나의 문제는 단 한 번만 풀도록 하는 알고리즘

---

다음 가정이 만족하는 조건에서 사용할 수 있다.

🌱 Dynamic Programming 조건

1. Overlapping Sub-problems :

큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.

• 예시 : 피보나치 수열
  - 첫째와 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합과 같은 수열이다.

  function fib(n) {
  	if(n <= 2) {
  		return 1;
  	};
  	return fib(n - 1) + fib(n - 2);
  }
  // 1, 1, 2, 3, 5, 8... 
  // 재귀함수로 구현한 피보나치 수열 

+ Memoization

동적 프로그래밍에선 작은 문제들이 반복되고, 이 작은 문제들의 결과값이 항상 같다.
그래서 이를 이용해 한번 계산한 작은 문제를 저장해놓고 재사용한다

2. Optimal Substructure :

작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

• 정답 : 최적의 해결방법을 의미
• 주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법을 찾아야 한다.
• 작은 문제들의 최적의 해법을 결합하면 결국 준체 문제의 최적의 해법을 구할 수 있다.

---

🌱 정리

• Dynamic Programming을 적용하기 위해서는, 작은 문제의 최적 해법을 결합하여 최종 문제의 최적 해법을 구할 수 있어야 한다.
• 작은 문제들이 반복된다
• 같은 문제는 구할때마다 정답이 같다
• DP는 큰 문제를 작은 문제들로 분할하고 이를 이용해 큰 문제를 해결하는 방법이다.
• 분할정복과 다른점은 DP의 경우엔 작은 부분 문제의 답이 늘 같아야 한다는 것이다.