기초 (7) 동적 계획법

[Dynamic Programming, 동적 계획법]

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

탐욕법 Greedy Algorithm은 작은 단계에서 최선의 방법만 고려하지만,
동적계획법은 작은 단계에서 모든 방법을 계산한다는 차이점이 있다.​

• 일부 단계에서는 최선이 아닌 방법들이 전체 문제에서 최적방법이 되는 경우를 고려한다.
• 완전탐색과는 달리, Memoization을 사용한다.
• 계산한 부분문제들의 데이터를 별도 메모리에 저장하여,
  추후 같은 계산이 필요한 경우 상수시간만에 해당 값을 호출한다.
• 문제를 읽고 점화식을 어떻게 구성하는지에 따라 복잡도가 확연히 달라진다.

ex) 거스름돈을 얼마나 지급할 것이냐.

[탐욕법]
1000원짜리부터 최대한 많이 사용해서 동전의 개수를 줄인다.

[동적 계획법 ]
모든 경우의 수를 생각해서 가작 적은 개수의 동전을 줄 수 있는 경우를 찾는다.

---

< 사용 조건 >

2가지 조건을 만족하는 문제에는 동적 계획법을 적용할 수 있다.

1. Overlapping Subproblems
   동일한 작은 문제들이 반복하여 나타나는 경우
2. Optimal Substructure
   부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우