Dynamic Programming

1. Dynamic programming

 1) Outline

  : 다이나믹 프로그래밍이란, 문제의 size가 클때 문제를 sub problem으로 나누어서 해결하여 전체를 해결하는 기법을 말한다. 언뜻 보면 Divide & Conquer와 비슷하지만 분명한 차이점이 존재한다.

- Divide&Conquer 전략에서는 sub problem들의 solution들을 계산한 후에, 따로 저장하지 않아 그 해가 다른 sub problem에서 또 필요해질 때 재계산해야 할 수도 있다.

- 그렇지만 DP에서는 모든 subproblem의 값을 저장해놓기 때문에 한번 계산된 해는 재계산되지 않으며, 그 값을 그대로 사용한다. 따라서 Table을 만들어 값을 저장해둔다.

 

또한, DP는 재계산 등에 시간을 많이 소요하느니 공간을 소비하는 방법을 택해 시간을 최대한 줄이고자 한다. 

-> 따라서 sub problem들의 해가 계산이 되었다면, solution이라는 array에 저장을 해둔다.

- 만약 sub problem Q에 대한 solution이 이후에 필요할 때,

  1) 저장이 안되어있다면 다시 Q를 recursive call 해서 값을 재계산한다.

  2) solution이 저장되어있다면 그 값을 그대로 불러와 사용(Retrieve), 재귀호출은 하지 않는다.

 

 

EX) 피보나치 수열 - DP로 해결할 수 있다.

 

 

2) Matrix-Chain Multiplication

: 이 문제를 Dynamic Programming으로 해결할 수 있다.

A1,A2...An개의 행렬이 주어졌을때 이를 차례대로 곱하게 되는데, 어떤 순서로 행렬을 곱하면 최소 수의 곱셈 연산을 이용해 N개의 행렬을 곱할 수 있는지 알아내라. -> 즉, 행렬들의 곱셈 순서를 결정하라,

 

- 행렬들은 기본적으로 앞 행렬의 열과 뒤 행렬의 행이 같아야 곱셈이 가능하다.

: Matrix A=pxq, Matrix B=qxr 이면 결과적으로 Matrix C=pxr 가 나오게 된다.

-> 예시를 보면 같은 결과가 나오더라도 행렬을 계산하는 순서에 따라 계산 횟수가 현저하게 차이가 남을 확인할 수 있다.

 

-> 그렇다면 체계적으로 어떻게 해야 가장 적은 횟수의 행렬 순서를 도출할 수 있을까?

 

 

- Development

1) 최적해를 도출해내는 구조를 파악해야 한다. 즉, sub problem들로 구성되어있고, sub problem의 해가 또 호출되는 등 문제가 재귀적으로 생겼는지를 파악해야 한다.

 

2) 이 구조를 점화식& 테이블 형태로 정의해야 한다. 테이블은 두가지 종류가 존재하는데, 값만 알고싶은지, 그 해가 도출되는 방법을 알고 싶은지에 따라구현이 다르다. 

EX) Diijkstra 알고리즘에서 shortest path 값 뿐만 아니라 앞 vertex의 값을 저장해두면 경로까지 복원할 수 있다.

 

3) bottom-up 방식으로 최적해의 값을 계산한다.

4) 계산된 정보를 토대로 해서 단계적으로 최적해를 만들어간다. : 이 단계별로 값은 모두 저장해두어야 한다.

 

 

이 과정을 위 문제에 대해 단계별로 수행해보자.

 

- Phase 1) 구조 파악

-> Ai~Aj 까지의 matrix를 k를 기점으로 하여 둘로 쪼갠다. 이때 k가 어디로 결정되냐에 따라 j-i가지 방법이 존재할 수 있다.

Ai~Aj까지의 총 비용은 Ai~Ak까지 계산한 비용+Ak+1~Aj까지 계산한 비용+ 둘 결과를 곱한 비용이다.'

Phase 2) 이를 점화식으로 만든다.

- 한 테이블에 두가지 값을 저장하는데 m[i,j] 에는 총 계산 횟수를 저장하고, s[i,j]에는 그 최소 횟수를 만드는 k를 저장한다.

m[i,j]에는 이 사이를 k로 쪼갰을때 가장 적은 횟수가 나오는 값을 저장하는 것이다.

 

예를 들어 m[1,10]을 m[1,3],m[4,10]으로 쪼개고, m[1,3]을 m[1,2],m[2,3]으로 쪼갰을때,

m[2,10]을 m[2,3],m[4,10]으로 쪼개면 이전에 m[1,10]을 쪼갤 때 나왔던 m[4,10]과 m[2,3]이 다시 호출되는 양상을 확인할 수 있다. -> 즉 재귀적 양상을 확인할 수 있다. 재계산하는 대신 저장해둔 값을 사용한다.

 

Phase 3) 값을 계산한다.

-> 재귀적으로 계속 호출되는 값을 매번 재계산 하는 거보다 n*n개의 table에 값과 k를 저장해두는게 훨씬 효율적이다.

-> 값을 저장해두고 계속 호출되는 것을 확인할 수 있다. 가장 최선의 방법을 찾아서 k값과 총 비용을 저장해두는 것을 확인할 수 있다.

 

Step 4) 최적해를 출력하는 구조를 만든다.

-> 테이블을 참조해 값을 출력한다.

 

 

-> 예시를 통해 Dynamic Programming으로 문제를 해결하는 방법을 알아볼수 있었다.