동적 프로그래밍(Dynamic programming)

동적 프로그래밍(Dynamic programming)

 - 하위의 작은 문제들을 풀고, 이를 이용해서 더 큰 문제를 풀어나가는 방법

 - 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것

 - 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용

 - 동적 계획 알고리즘은 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용

 

그리디 알고리즘 비교

 - 동적 프로그래밍은 가능한 모든 방법을 고려해야 한다는 단점

 - 그리디 알고리즘은 항상 최적해를 구해주지는 않지만, 다행히 Minimum Spanning Tree(최소 신장 트리 문제) 등의 여러 문제에서 그리디 알고리즘이 최적해를 구할 수 있음이 이미 입증되었다.

 

이해

동적 프로그래밍의 유명한 문제로 배낭문제가 있다.

크기가 5인 가방에 최대한 가치있는 물건을 넣는 방법은?

물건	무게	가치
노트북	4	5000
책	2	3000
키보드	3	3500

1. 먼저 가방의 크기와 물건의 표를 만들자

	1	2	3	4	5
노트북
책
키보드

2. 노트북은 무게가 4이므로 1,2,3 에는 넣을 수 없으므로 가치가 0이고 4부터 가치가 5000이다.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책
키보드

3. 책도 노트북과 마찬가지 방법으로 가치를 적어보자.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책	0	3000	3000
키보드

4. 크기가 4인 곳에서는 책보다 노트북을 가지고 가는것이 더 가치가 있으므로 노트북을 선택한다.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책	0	3000	3000	5000	5000
키보드

5. 키보드도 마찬가지로 해본다.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책	0	3000	3000	5000	5000
키보드	0

6. 크기가 2인 곳에서는 책을 가지는 것이 더 가치가 있으므로 책을 선택한다.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책	0	3000	3000	5000	5000
키보드	0	3000

7. 크기가 3인 곳에서는 키보드를 가지는 것이 더 가치가 있으므로 키보드를 선택한다.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책	0	3000	3000	5000	5000
키보드	0	3000	3500

8. 크기가 4인 곳에서는 노트북이 더 가치가 있으므로 노트북을 선택한다.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책	0	3000	3000	5000	5000
키보드	0	3000	3500	5000

9. 크기가 5인 곳에서는 책과 키보드를 선택할 수 있으므로 두 물건의 가치인 6500이 된다.

	1	2	3	4	5
노트북	0	0	0	5000	5000
책	0	3000	3000	5000	5000
키보드	0	3000	3500	5000	6500

따라서 답은 6500이 된다.

 

좀 더 이해하기

4, 9번이 이해가 안될 수도 있는데, 일단 각 라인은 각 물건이 중심이 된다.

주황색 값을 계산할 때는 

1. 파랑색 가치 + 책 가치 : 총 크기가 4

2. 빨강색 가치

3. 초록색 가치

위 3개중에 가장 큰 값이 된다.

빨강색 가치가 가장 크므로 5000원이 된다.

 

그리고 다음은

위와 같은 방식으로 진행하면 된다.

 

참고

사이트 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95