동적프로그래밍에서는
1. 동적프로그래밍을 사용할 수 있는 문제
2. 행렬 경로 문제
3. 돌 놓기 문제
4. 행렬 곱셈 순서 문제
5. 최장 공통부분 순서 LCS
로 나누어져있다.
1. 동적프로그래밍을 사용할 수 있는 문제
우선 , 동적 프로그래밍은 다른 크기의 문제들이 서로 재귀적 관계를 가졌을 때에 재귀호출 알고리즘이 효율적이지 못하여 중복 호출이 많이 발생했을 시에 사용하면 좋은 기법이다.
※여기서 재귀 호출이란 ??
(Recursive call) 함수란 하나의 작업을 수행하기 위해 독립적으로 설계된 프로그램 코드의 집합이다.
재귀호출 함수란 함수 내부에서 자기 자신을 또 다시 호출하는 행위를 의미하는데, 이러한 재귀 호출은 자기 자신을 계속해서 호출해서 끊임없이 반복되게 된다. 무한 반복을 막기 위해 함수내 호출 중단되는 명령문을 포함시키는 것이며,
재귀호출을 사용함으로써 복잡한 문제도 매우 간단하고 논리적이게 접근하여 표현할 수 있게 된다.
재귀호출의 장점 : 코드의 간결함
재귀호출의 단점 : 무한 재귀호출의 위험성, 성능 상의 문제
피보나치 수를 구하기 동적프로그래밍은의 개념을 쉽게 이해할 수있는데,
f(n) =f(n-1)+f(n-2)
f(1)=f(2)=1
즉, n의 피보나치 수는 n-1 의 피보나치 수와 n-2의 피보나치 수를 포함하고 있다.
이 처럼 동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 표현 되었다고 하고, 이를 최적 부분 구조를 가졌다고 한다. 동적프로그래밍을 사용하려면 이 성질을 기억해야한다.
중복된 호출을 피하는 방법을 피한 것을 특별히 메모하기라는 이름을 붙였으며, 이를 메모제이션 Memoization 이라 한다. 이 방식은 동적프로그래밍의 하향식 방법이다.
바텀업 방식의 아래에서 위로 저장해 가면서 해를 구해 나가는 방식도 있고 이 방식이 더욱 사용 되지만, 두 가지 전부 동적 프로그래밍 모두 작은 무제들의 해를 테이블에 저장해 나간다는 점이 동일하다.
재귀적호출에서의 피보나치를 구하는 방법
#include <iostream>
int Fibonacci(int n){
if (n <= 0) return 0;
else if (n == 1) return 1;
else return Fibonacci(n - 1) + Fibonacci(n - 2);
}
알고리즘으로 피보나치를 구하는 방법
#include <iostream>
int Fibonacci(int n) {
int fib[n];
for (int i = 2; i < n; i++) {
fib[0] = 0;
fib[1] = 1;
fib[i] = fib[n-1] + fib[i-2];
}
return fib[n];
}
2. 행렬 경로 문제
동적 프로그래밍에서 피보나치 수 구하기 보다는 복잡할 수가 있지만 행렬 경로 문제를 살펴보자.
규칙 : 양 또는 음의 정수 원소들로 구성된 n X n 행렬이 주어지고, 행렬의 좌상단에서 시작해서 우하단까지 이동 한다.
오른쪽이나 아래쪽으로만 이동할 수 있다.
왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.
행렬의 좌상단에서 우하단까지 방문한 수들의 더한 값이 최대화가 되도록 한다.
| 6 | 7 | 12 | 5 |
| 5 | 3 | 11 | 18 |
| 7 | 17 | 3 | 3 |
| 8 | 10 | 14 | 9 |
빨간색 글씨의 방향 대로 가려 한다.
int matrixPath(int[][]m,int i,int j){//(i,j) 에 이르는 최고점수를 구하자
if(i==0&&j==0)return [i][j]; //i가 0이거나 j가 0이면 참이면 i,j를 반환하라
else if(i==0) return matrixPath(m,1,j-1)+m[i][j]; //오른쪽 수평이동해라
else if(j==0) return matrixPath(m,i-1,1)+m[i][j]; //아래쪽 수직 이동해라
else return Math.max(matrixPath(m,i-1,j),matrixpath(m,i,j-1)+m[i][j];//합산하라
}
이 알고리즘으로 구현하게 되면 재귀호출로 인한 알고리즘 성능 저하가 일어나게 된다.
배열에 값을 저장해서 사용하는 메모이제이션 기법을 사용하여 개선해보도록 한다.
행은 i 열은 j
m (i,j):(i,j) 에 해당하는 방의 값
c (i,j):(i:,j) 까지 최적의 경로로 왔을 때 최댓값
c(i,0) = c(i-1, 0) + m(i,0), i>0 //맨 왼쪽에 있는 방의 경우
c(i,j) = Max(c(i-1,j), c(i,j-1)) + m(i,j), i>0, j>0 //일반적인 경우, 위 혹은 왼쪽 중 최대인 곳 + 자신의 값
int matrixPath(int[][] m, int i, int j, int[][] cache) {
if(i == 0 && j == 0) return cache[0][0]; // 첫번째 행, 열 이 0이면 첫번째 행 과 열을 나타내라
else if (i == 0) { cache[i][j] = (cache[0][j - 1] != 0) ? (cache[0][j - 1] + m[0][j]) : (matrixPath(m, 0, j - 1, cache) + m[0][j])
return cache[i][j]; //오른쪽에서 수평이동을 할것이다. i == 0 인것은 열이 고정인 상태 인것이고,
//cache[0][j-1]=0이 맞으면 :기준의 첫번째를 실행하고 아니면 뒤에것을 실행하라 [j-1]은 그 다음의 숫자를 나타내는 것이고, m[i][j]는 현재위치를 나타낸다.
//이렇게 계속 최적의 경로를 찾아 나가는 것이다.
}
//
else if (j == 0) {
cache[i][j] = (cache[i - 1][0] != 0) ? (cache[i - 1][0] + m[i][0]) : (matrixPath(m, i - 1, 0, cache) + m[i][0])
return cache[i][j]; //위에서 아래로 이동할 것이다. j==0 인것은 행이 고정인 상태인 것이고, 위의 내용과 동일하다.
}
int a = (cache[i - 1][j] != 0) ? (cache[i - 1][j]) : (matrixPath(m, i - 1, j, cache));
int b = (cache[i][j - 1] != 0) ? (cache[i][j - 1]) : (matrixPath(m, i, j - 1, cache));
cache[i][j] = Math.max(a, b) + m[i][j];
} //한줄의 행과 열을 제외한 3by3의 최적의 경로를 구하는 것이다. max의 값을 구해서 현재의 값을 더해가면서 최적의 경로를 구한다.
3. 돌 놓기 문제
3XN 테이블의 각 칸에 숫자가 쓰여 있다. 테이블의 각 칸 중 일부에 제한 조건을 만족하는 방법으로 돌을 놓아 돌이 놓인 곳에 있는 수의 합을 최대로 하는 문제이다.
제한 조건은
가로나 세로로 인접한 두 칸에 동시에 돌을 놓을 수 없다.
각 열에는 적어도 하나 이상의 돌을 놓는다.
int pebble(int i, int p) {
// i열이 패턴 p로 놓일 때의 최고점수
// w(i, p) : i열이 패턴 p로 놓일 때 i열에 돌이 놓인 곳의 점수합
if (i == 1)
return w[1, p];
else {
max = 0;
for (int q = 0; q < 4; ++q) {
if (패턴 q과 패턴 p가 양립) {
tmp = pebble(i - 1, q);
if (tmp > max) max = tmp;
}
}
return max + w(i, p);
}
}
4. 행렬 곱셈 순서 문제
5. 최장 공통부분 순서 LCS
두 string 에 공통적으로 들어있는 common subsequence 들 중 가장 긴 것을 찾는 것인다.
func lcs(x,y)
if ( length(x)=0 or length(y)=0 )
return "" best = lcs(x[1,n-1],y[1,m])
if ( length(best) < length(lcs(x[1,n],y[1,m-1])) ) best = lcs(x[1,n],y[1,m-1])
if ( x[n] = y[m] and length(best) < length(lcs(x[1,n-1],y[1,m-1]) + 1 )
best = lcs(x[1,n-1],y[1,m-1]) + x[n]
return best
func lcs(x,y)
n = length( x ), m = length( y )
for i from 0 to n for j from 0 to m
if ( i is 0 or j is 0 )
table[i,j] = ""
if ( x[i] == y[j] )
table[i,j] = x[i] else /* Sentinel */ table[i,j] = table[i-1,j]
if ( length( table[i,j] ) < length( table[i,j-1] ) )
table[i,j] = table[i,j-1];
if ( x[i] = y[j] and length( table[i,j] ) < length( table[i-1,j-1] ) + 1 )
table[i,j] = table[i-1,j-1] + x[i];
return table[n][m]