다이나믹 프로그래밍

개요

큰 문제를 작은 문제로 나눠서 푸는 알고리즘
다이나믹 프로그래밍의 역사

조건

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

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

• 피보나치수

2. Optimal Substructure (최적 부분구조)

• 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
• 예시 )
  서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면, 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.
• Optimal Substructure를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
  10번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
  9번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
  …
  5번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
  4번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
  4번째 피보나치 수는 항상 같다.

구현방식

1. Top-down (재귀)

피보나치수

2. Bottom-up (반복문)

1. 문제를 크기가 작은 문제부터 차례대로 푼다.
2. 문제의 크기를 조금식 크게 만들면서 문제를 점점 푼다.
3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
4. 반복하다 보면 가장 큰 문제를 풀 수 있다.

코드

int d[100];
int fibonacci (int n) {
	d[0] = 0;
	d[1] = 1;
	for (int i = 2; i<=n; i++) {
		d[i] = d[i-1] + d[i-2];
	}
	return d[n];
}

결론

• 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.
• Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.
• 따라서, 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다.
• 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.
• 메모를 한다고 해서 영어로 Memoization이라고 한다.