Dynamic Programming
- 동적 계획법
- 다이나믹 : 별 다른 의미 없이 사용된 단어다. 잘못 쓰였다.
필요한 상황
- 최적 부분 구조
Optimal Substructure
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
- 중복되는 부분 문제
Overlapping Subproblem
동일한 작은 문제를 반복적으로 해결해야 한다.
분할정복 Divide and Conquer와 차이점
- 분할정복 : 작은 문제가 반복되어 나오지 않음. 큰 문제를 해결하기 어려워서 작은 문제로 나누어 푸는 것이 분할정복법
- 동적계획 : 작운 문제들이 반복되어야 동적계획.
Memoization
- 작은 문제들이 반복되는 동적 프로그래밍에서 한 번 계산한 작은 문제를 저장해놓고서 다시 사용을 한다.
- 예를 들면, 피보나치의 수는
N번째 수열 = N-1번째 수열 + N-2번째 수열이라는 점화식을 갖는데, 이는 N이 증가할 때마다 함수의 수가 기하급수적으로 증가한다. 이 반복적으로 호출되는 함수의 결과값을 저장해놓고서 다시 사용을 하는 것이 메모이제이션이다.
피보나치 수열 예시
- 작은 문제들이 반복된다.
- 같은 문제는 구할 때마다 정답이 같다.
Top-down
1
2
3
4
5
6
7
8
9
10
public class Main {
public static long[] d = new long[100];
public static long fibo(int x) {
if (x == 1 || x == 2) return 1;
if (d[x] != 0) return d[x];
d[x] = fibo(x - 1) + fibo(x - 2);
return d[x];
}
}
Bottom-up
1
2
3
4
5
6
7
8
9
10
11
12
public class Main {
public static long[] d = new long[100];
public static void main(String[] args) {
d[1] = 1;
d[2] = 1;
int n = 50; // 50번째 피보나치 수 찾기
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
}
}
