알고리즘 ch10 Dynamic Programming

Dynamic Programming

- 큰 문제를 작은 문제로 나눠서 푸는 문제

- Optimization problem 푸는 방법 중 하나이다.

  * divide and conquer과 다른점 : 메모리를 이용해 중복 계산을 하지 않는다.

- 풀이 과정

 ① 문제 특성을 파악

 ② 점화식 정의

 ③ 점화식대로 계산 수행

- 두가지 방식으로 나뉨

 1) Top-down 방식 : recursion -> memoization

 2) Bottom-up 방식 : Loop

- dp로 풀수있는 optimization problem 

  예시)

 Matrix-Chain Multiplication problem : 두 개 이상의 행렬의 순서가 주어질 때 행렬의 곱셈에서 곱셈 연산의 수를 최소화하는 방법을 찾는 것

행렬의 곱 ABCD 에 대해 행렬은 결합법칙이 성립하므로

$\left(\right(AB\left)C\right)D=\left(\right(A\left(BC\right)\left)D\right)=\left(AB\right)\left(CD\right)=A\left(\right(BC\left)D\right)$가 성립한다. 

이때 각각의 연산마다의 곱셈 연산의 횟수는 다르므로 이중에서 최소 연산 횟수를 가지는 방법을 찾아야 한다.

예를 들어 $A=10\ast 30,B=30\ast 5,C=5\ast 60$ 의 크기를 가지는 행렬의 곱셈을 진행 할때

$$\left(AB\right)C=(10\ast 30\ast 5)+(10\ast 5\ast 60)=1500+3000=4500\left(countofoperations\right)$$

$$A\left(BC\right)=(30\ast 5\ast 60)+(10\ast 30\ast 60)=9000+18000=27000\left(countofoperations\right)$$

위처럼 괄호의 위치마다 연산의횟수는 크게 차이가 나기때문에 최적의 방법을 찾아내는것이 중요하다.

bottom up 방식을 이용해서 풀 것이다.

사용 점화식

M[i][j] = 행렬 i부터 j까지 행렬을 곱하는데 필요한 곱셈의 최소 횟수

시간복잡도 O(n^3)     공간복잡도 O(n^2)