[알고리즘] Dynamic Programming (동적계획법)

Dynamic Programming

1. 개요

한국어로 번역하면 동적 계획법 혹은 동적 프로그래밍.

말이 좀 이상하게 붙었는데, 프로그래밍이 아니고 테이블을 붙이면 이해가 빠르다.

즉 dynamic table을 만들어서

계산을 해감에 따라 테이블에 계산값을 저장하고,

그 다음 번 계산을 할 때는 처음부터 계산하는게 '아니'고

테이블에 저장된 값을 보고 계산을 한다

이게 포인트. 

2. 정의

대체로 두 가지 조건을 만족하면 다이나믹 프로그래밍으로 풀 수 있다.

1) Optimal substructure 

2) Overlapping problems

- Optimal substructure ?

: 문제의 최적해가 부분문제의 최적해로 구성된 것을 일컫는다.

쉽게 말해서 전체 문제의 답은 서브 문제의 답으로 구성된다는 것 (동어반복아니냐?)

예를 들어서 0/1 knapsack 문제에서

답이 n개의 물건으로 구성됐다고 하면

n번의 선택이 이루어졌을 거다. (물건을 n개 넣으려면 n번 선택을 해야 넣을 거 아니냐)

이때, n번 선택 각각의 상황을 subproblem으로 보면

문제 전체의 최적해는 이 sub 최적해로 구성이 된다는 거.

뭐 느낌적인 느낌만 알면 되고 중요한 건 증명법

(1) k 번째 선택이 최적해라고 가정하고

(2) k-1 번째 선택으로 되돌아가서 상황을 좀 바꾼 다음에

(3) 모순을 일으킨다. (!!)

예를 들어보겠는데 다시 0/1로 돌아와서, 

(1) v/w 순으로 물건을 넣어서 뭐 어쨌든 최적해를 찾았다 치자.

(2) 이 물건이 n개로 구성돼있으면 n번째로 들어간 걸 빼보자.

그럼 n-1개의 물건이 들어간 꾸러미(knapsack)가 있을 텐데

만약 이 n-1의 꾸러미가 최적이 아니라면, (=그러니까 전체 문제의 최적해가 부분문제의 최적해로 구성돼있지 않다면)

n-1개로 구성된 더 나은 꾸러미 후보가 있다는 소리지?

거기에 아까 빼낸 n번째 물건을 넣으면 

(3) n개로 구성된 '더 나은'(=최적해인) 꾸러미가 등장. 그럼 (1)의 가정에 모순이지.

따라서 0/1 knapsack 문제는 Optimal substructure 구성을 가지고 있음

- Overlapping?

이것도 간단한게, 아니 다이나믹 프로그래밍의 개요를 뭐라고 그랬는지 생각해보자.

테이블에 계산값을 저장해놓고, 필요할 때마다 쳐다보면서 푼다고 했다.

그걸 참조를 왜 하겠어? 자주 보니까 그렇겠지. 뭐 그런 것처럼

0/1 knapsack 문제에서도 잘 생각해보면

n개로 구성된 최적의 꾸러미를 찾으려면

n-1번째까지 최적해를 찾은 다음에

거기에 들어갈 수 있는 이것저것을 다 넣어보고

그 중에서 제일 나은 놈을 n번째 최적꾸러미로 저장해야 할 것 아니냐.

근데 그렇게 하려면 n-1번째 최적해가 계속 계산에 사용되지?

그걸 테이블에 저장해두고 자주 보는 거고

중복 사용하니까 말 그대로 overlap.

3. 예시

- Assembly Line Problem

- Matrix Chain Multiplication Problem

- 0/1 Knapsack Problem 

정도?