Dynamic Programming
→ Richard Bellman 이 구성함
ex) 피보나치 수열
int fib (int n) {
if (n == 1 || n == 2)
return 1;
else
return fib(n-2) + fib(n-1);
}
Java
복사
f(n) = f(n-1) + f(n-2). : n > 2
f(1) = f(2) = 1
→ 이 함수의 진행과정은 많은 계산이 중복이 된다 → 매우 비효율적
중복을 피하는 방법 1, Memoization, Caching
→ 이미 계산된 f값을 버리지말고, 기억을 해놓자! → Memoization
→ 배열에 중간 결과를 저장해놓는다 → caching 한다
→ 중간 계산 결과를 caching함으로써 중복 계산을 피함
int fib (int n) {
if (n == 1 || n == 1)
return 1;
else if (f[n] > -1) // 배열 f가 -1로 초기화되어 있다고 가정
return f[n]; // 즉 이미 계산된 값이라는 의미
else {
f[n] = fib(n-2) + fib(n-1); // 중간 계산 결과를 caching
return f[n];
}
}
Java
복사
중복을 피하는 방법 2, Bottom-up 방식
int fib (int n) {
f[1] = f[2] = 1;
for (int i = 3; i <= n; i++)
f[n] = f[n-1] + f[n-2];
return f[n];
}
Java
복사
Ex2) 이항 계수 (Binomial Coefficient)
nCk → n개 중에서 k개를 선택하는 경우의 수
→ 위 공식대로 코드를 짜면 → 중복이 불가피하고 비효율적이다
int binomial(int n, int k) {
if (n == k || k == 0)
return 1;
else
return binomial(n - 1, k) + binomial(n - 1, k - 1);
Java
복사
그러면
int binomial(int n, int k) {
if (n == k || k == 0)
return 1;
else if (binom[n][k] > -1) // 배열 binom이 -1로 초기화되어 있다고 가정
return binom[n][k];
else
binom[n][k] = binomial(n-1, k) + binomial(n-1, k-1);
return binom[n][k];
}
}
Java
복사
DP : Bottom-up 방식
int binomial(int n, int k) {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= k && j <= i; j++) {
if (k == 0 || n == k)
binom[i][j] = 1;
else
binom[i][j] = binom[i-1[j-1] + binom[i-1][j];
}
}
return binom[n][k];
}
Java
복사
Memoization VS Dynamic Programming
•
순환식의 값을 계산하는 기법들이다
•
둘 다 DP의 일종으로 보기도 한다
•
Memoization은 Top-down 방식이며, 실제로 필요한 subproblem만을 푼다
•
동적계획법은 Bottom-up 방식이며, recursion에 수반되는 overhead가 없다
ex) 행렬 경로 문제
방법) 순환식 → 계산
목표 (i, j)에 도달하기 위해서는
→ (i, j-1)을 거치거나
→ (i-1, j)를 거쳐야한다
또한 (i, j-1) 또는 (i-1, j) 까지는 최선의 방법으로 이동해야 한다
L[i, j] : (1, 1)에서 (i, j)까지 이르는 최소합
=
•
if i = 1 and j = 1
•
, if j = 1
•
, if i = 1
•
Recursive Algorithm
int mat(int i, int j) {
if (i == 1 && j == 1)
return m[i][j];
else if (i == 1)
return mat(1, j-1) + m[i][j];
else if (j == 1)
return mat(i-1, 1) + m[i][j];
else
return Math.min(mat(i-1, j), mat(i, j-1)) + m[i[j];
}
Java
복사
→ 비효율적 (했던 계산 하고 또하고를 반복한다, 중복)
Memoization
int mat(int i, int j) {
if (L[i][j] != -1)
return L[i][j];
if (i == 1 && j == 1)
L[i][j] = m[i][j];
else if (i == 1)
L[i][j] = mat(1, j-1) + m[i][j];
else if (j == 1)
L[i][j] = mat(i-1, j) + m[i][j];
else
L[i][j] = Math.min(mat(i-1, j), mat(i, j-1)) + m[i][j];
return L[i][j];
}
Java
복사
Bottom-up
int mat() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 && j == 1)
L[i][j] = m[i][j];
else if (i == 1)
L[i][j] = m[i][j] + L[i][j-1];
else if (j == 1)
L[i][j] = m[i][j] + L[i-1][j];
else
L[i][j] = m[i][j] + Math.min(L[i-1][j], L[i][j-1]);
}
}
return L[n][n];
}
Java
복사
→
Common Trick
/* initialize L with L[0][j] = L[i][0] = ∞ for all i and j */
int mat() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 && j == 1)
L[i][j] = m[1][1];
else
L[i][j] = m[i][j] + Math.min(L[i-1][j], L[i][j-1]);
}
}
return L[n][n];
}
Java
복사
→ 지금까지 한 건 경로를 구한 것이 아니라, 최소합만 구했다
경로를 구한다면?
/* initialize L with L[0][j] = L[i][0] = ∞ for all i and j */
int mat() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 && j == 1)
L[i][j] = m[1][1];
P[i][j] = '-';
else {
if (L[i-1][j] < L[i][j-1] {
L[i][j] = m[i][j] + Math.min(L[i-1][j], L[i][j-1]);
P[i][j] = '↑';
}
else {
L[i][j] = m[i][j] + L[i][j-1];
P[i][j] = '←';
}
}
}
}
return L[n][n];
}
void printPath() {
int i = n; j = n;
while (P[i][j] != '-') {
print(i + " " + j);
if (P[i][j] == '←')
j = j - 1;
else
i = i - 1;
}
print(i + " " + j);
}
Java
복사
동적계획법
1.
일반적으로 최적화문제(optimisation problem) 혹은 카운팅(counting) 문제에 적용됨
2.
주어진 문제에 대한 순환식(recurrence equation)을 정의한다
3.
순환식을 memoization 혹은 bottom-up 방식으로 푼다
Matrix-Chain Multiplication
행렬의 곱셈
p x q 행렬 A와 q x r 행렬 B 곱하기
// 기본적인 행렬 곱셈 알고리즘
void product(int A[][], int B[][], int C[][]) {
for (int i = 0; i < p; i++) {
for (int j = 0; j < r; j++) {
C[i][j] = 0;
for (int k = 0; k < q; k++)
C[i][j] += A[i][k] * B[k][j];
}
}
}
Java
복사
→ 곱셈연산의 횟수 = pqr