1. 다이나믹 프로그래밍 이란?
- Space(공간)을 더 사용하여 re-computing(중복되는 연산)을 방지하여
Speed(속도)를 증가시켜주는 방법입니다..
- solution 테이블을 사용하여 이미 연산된 적이 있다면 그 값은 바로 테이블에서 가져와서 쓰는 것입니다.
- 처음하는 연산의 경우 연산을 수행한 뒤 결과값을 solution table에 저장합니다.
- 일반적으로 최적해(Optimal Solution)을 구하는 데에 많이 사용된다.
2. Divide and Conquer(분할정복)과 차이점?
- 분할정복 역시 큰 문제를 작은 문제로 쪼개서 해결한다.
- 차이점은 DP에서는 부분(작은) 문제의 해가 중복되는 부분이 있어 나중에 또 필요하다는 것.
3.대표적인 예시
(1) 피보나치 수열
-피보나치 수열을 모든 연산을 반복적으로 수행하게끔 구현하면 n이 증가함에 따라
총 연산의 수 가 급격히 높아진다.(중복되는 연산이 매우 많음)
-f(6)만 해도 이렇게 중복되는 연산이 많습니다.
- 빨간색은 연산없이 바로 테이블에서 끌어오는 녀석입니다.
(2) Matrix-Chain Multiplication 문제
- n개의 행렬이 주어졌을 떄 곱셈연산수를 가장 적게 하는 방법을 찾아라.
- (1~n)을 (1~k) * (k~n)으로 나누어야 하는데 어디를 나눌 것인가?
- 점화식과 관련이 깊다.
4. 해결절차
- (1) 최적해를 정의 한다.
- (2) 이를 바탕으로 점화식으로 표현한다
- (3) 바텀업방식이나 탑다운방식으로 이를 계산해 나간다.
5.구현방식
-(1) 바텀업 방식(Bottom-Up Approach)
: 반복문 사용
문제의 전체적인 구조를 파악하고 있어야 한다.
재귀를 사용할 때의 오버헤드를 줄일 수 있다.
-(2) 탑다운 방식(Top-Down Approach)
: 점화식의 구조를 직관적으로 파악하기 편하다.
재귀함수 사용