다이나믹 프로그래밍

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

* 크다와 작다는 문제의 크기를 의미.

 

 

- 큰 문제를 작은 문제로 나누는 알고리즘에는 2가지 종류가 있음

1. 다이나믹 프로그래밍(DP)

2. 분할 정복(D&C)

* 다이나믹 프로그래밍은 작은 문제들이 중복이 가능하지만, 분할 정복은 작은 문제들끼리 중복이 되지 않는다.

 

 

- 다이나믹으로 풀 수 있는 문제의 속성

 

1. Overlapping Subproblem : 겹치는 부분(작은) 문제

ex) 피보나치 수 : (0,1,1,2,3,5,8,13,21,34,55...)

Fn = F(n-1) + F(n-2) 

여기서 Fn이 큰 문제이고, 나머지 F(n-1)과 F(n-2)가 작은 문제라고 할 수 있다.

하지만 작은 것은 상대적인 개념이므로 F(n-1)을 구할 때는 F(n-1)이 큰 문제가 된다. 

* 큰 문제와 작은 문제를 같은 방법으로 풀 수 있기 때문에 주로 재귀를 사용한다.

 

2. Optimal Substructure : 문제의 정답은 작은 부분의 정답을 통해서 구할 수 있는 문제

ex) 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면,

대전에서 부산을 가는 가장 빠른길은 대구를 거쳐야 한다. 

만약에, 대전에서 부산을 가는 가장 빠른길이 대구가 아닌 울산을 거쳐야 한다면, 

서울에서 부산을 가는 가장 빠른 길 또한 대구를 거치는 것이 아닌 울산을 거쳐야 한다. 

* Optimal Substructure을 만족한다면 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정해야 한다.

예를 들어, 10번째 피보나치를 구하면서 구한 4번째 피보나치 수는, 9번째 피보나치를 구하면서 구한 4번째 피보나치 수와 같아야 한다. 

 

 

- 푸는 방법

# 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.

# Optimal SubStructure를 만족하기 때문에, 같은 문제는 구할 때 마다 정답이 같다.

# 따라서 정답은 한 번 구했으면, 어딘가에 메모를 해 놓는다.

# 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.

# 이런 메모를 하는 것을 영어로 Memorization 이라고 한다.

 

 

- 구현 방법 

1. Top-down 방식 

ex) 재귀

2. Bottom-up 방식

ex) 반복문

 

* 두 방식의 시간차이는 알 수 없다. 

* 문제에 따라 탑-다운으로 풀 수 있지만 바텀-업 으로는 풀 수 없는 경우가 존재한다. (그 반대도 해당)