[기초] 다이나믹 프로그래밍(Dynamic Programming, DP)

 

 

다이나믹 프로그래밍

 

 

큰 문제를 작은 문제로 나눠서 푸는 알고리즘으로 동적 계획법이라고도 합니다.

 

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

 

 

아래 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있습니다.

 

 

1. Overlapping Subproblem : 겹치는 부분 문제

 

2. Optimal Substructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때

 

 

---

Overlapping Subproblem

 

겹치는 작은 부분 문제로 나눠서 푸는 것이 핵심입니다.

 

 

문제 

작은 문제 - 작은 문제

(두 작은 문제가 겹쳐야 됨)

 

먼저 피보나치 수를 예시로 들어 알아보면,

 

- 피보나치 수 -

 

F(0) = 0

F(1) = 1

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

 

그러면 처음 피보나치 수를 몇개 써보면 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

 

그러면,

 

문제 : N번째 피보나치 수를 구하는 문제

작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

 

이렇게 볼 수 있습니다.

한번에 보면,

---

문제 : N번째 피보나치 수를 구하는 문제

작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

 

문제 : N-1번째 피보나치 수를 구하는 문제

작은 문제 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

 

문제 : N-2번째 피보나치 수를 구하는 문제

작은 문제 : N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

 

이렇게 다이나믹 프로그래밍이라면 작은 문제가 겹쳐야 합니다. 

(첫번째 성질 Overlapping Subproblem)

 

 

---

 

Optimal Substructure

 

문제의 정답을 작은 문제의 정답에서 구할 수 있습니다.

 

예를 들어, 

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

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

 

1. 서울 - 대전 - 대구 - 부산

2. 대전 - 대구 - 부산

 

이런 경우인데 만약 2번에서 대구가 아니라 울산을 거쳐 가는 길이 더 빠르게 되어버리면

 

대전 - 울산 - 부산 이므로 1번도 

서울 - 대전 - 울산 - 부산

 

 

 

 

 

그러면 피보나치 수는 문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있습니다.

 

 

그러면 문제의 크기의 상관없이 어떤 한 문제의 정답은 일정합니다.

 

그러면 N번째 피보나치 수는 항상 같습니다.

 

 

 

 

 

위 두가지 속성을 이용하여 다이나믹 프로그래밍을 완성할 수 있습니다.

 

 

 

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

 

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

 

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

 

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

 

 

 

마지막으로 문제에 접근할 때, 아래 두 가지 방법 중 선택하여 접근하면 됩니다.

 

 

문제를 작은 문제로 나누어, 작은 문제부터 푸는 Top - down

 

작은 문제를 모두 풀어가면서 점점 큰 문제를 푸는 Bottom - up

 

 

---

 

다이나믹 프로그래밍을 이용한 피보나치 수 구하기 소스입니다.

 

 

그냥 재귀함수만 사용하여 반복한다면 시간 초과가 될 수 있습니다.

 

int memo[100];

int fibonacci(int n) {
	if (n <= 1) {
    	return n;
    }
    else{
    	if (memo[n] > 0) { 
        	return memo[n];
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}