다이나믹 프로그래밍

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

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

1. Overlapping Subproblem - 겹치는 작은 문제
2. Optimal Substructure -최적 부분 구조

Overlapping Subproblem - 겹치는 작은 문제

- 피보나치 수

• Fn = Fn-1 + Fn-2 (n ≥ 2)
큰문제= 작은 문제
Fn-1 = Fn-2 + Fn-3

문제들이 겹친다.
• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
• 문제를 작은 문제로 쪼갤 수 있다

Optimal Substructure -최적 부분 구조

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

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

다이나믹 프로그래밍-DynamicProgramming

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

int fibonacci(int n) {
		if (n <= 1) {
			return n;
		} else {
			return fibonacci(n - 1) + fibonacci(n - 2);
		}
	}

->피보나치 수를 구하는 함수이다

메모하는 부분 추가

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];
		}
	}

정리

1.모든 문제를 풀어야한다.
2.모든 문제는 한번만 풀어야한다.
-> 시간 복잡도 : 문제의 개수 X 문제1개를 푸는 시간

다이나믹의 구현 방식에는 두 가지 방법

1. Top-down

1. 큰 문제를 작은 문제로 나눈다.
2. 작은 문제를 푼다.
3. 작은 문제를 풀었으니, 이제큰 문제를 푼다

-> Top-down은 재귀 호출을 이용해서 문제를 풀수 있다

2.Bottom-up

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

-> Bottom-up은 for문을 이용해서 풀수있다.

ex)

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];
	}

문제풀이 전략

1. 점화식을 먼저 정의
2. 문제를 작게 만들수 있는 방법을 찾아야한다.