들어가면서
다이나믹 프로그래밍의 개념을 정리해본다.
다이나믹 프로그래믹
재귀 호출(피보나치)
메모이제이션 코드 예시(Top-down)
int fib(int n){
if(n==1 || n==2) return 1;
else if(f[n] > -1) return f(n); // 배열 f가 -1로 초기화되어있다고 가정, 즉 이미 계산된 값이라는 의미.
else{
f[n] = fib(n-2) + fib(n-1); // 중간 계산 결과를 cashing
return f[n];
}아래는 bottom-up 코드 예시
int fib(int n){
f[1] = f[2] = 1;
for(int i = 3; i <= n; i++){
f[i] = f[i-2] + f[i-1];
}
return f[n];
}이항계수 (binomial)
nCk
int binomial(int n, int k){
if(n == k || k == 0) return 1; // base case
else return biniomial(n-1, k) + binomial(n-1, k-1); // recursion case
}많은 중복 계산 발생
recursion case가 base case로 도달하지 않으면 무한 루프에 빠진다.
n이 k보다 크거나 같다는 가정하에 어느 순간에 recursion case는 n = k, k = 0 조건을 만족하게 된다.(그렇게 설계해야 한다.)
이항 계수 메모이제이션 적용
int binomial(int n, int k){
if(n == k || k == 0) return 1;
else if(binom[n][k] > -1) return binom[n][k];
else{
binom[n][k] = binomial(n-1, k) + binomial(n-1, k-1);
return binom[n][k];
}
}이항 계수 bottom up 적용, 중복 계산 피함, 다이나믹 프로그래밍
2차원 배열에서의 bottom-up은 binom[i][j] = binom[i-1][j-1] + binom[i-1][j];
코드에서 왼쪽 항인 binom[i][j] up이고 , 오른 쪽 항인 binom[i-1][j-1] + binom[i-1][j]; bottom이다.
즉, 이미 주어져 있는 값이 bottom이라고 볼 수 있다.
int binomial(int n, int k){
for(int i = 0; i <= n; i++){ // 행 우선순위 탐색
for(int j = 0; j <= k && j <= i; j+=){ // k는 뽑는 횟수이다. j가 k보다 크게되면 주어진 k보다 뽑기를 많이 하겠다는 의미이다.
if(k==0 || n==k) binom[i][j] = 1;
else binom[i][j] = binom[i-1][j-1] + binom[i-1][j];
}
}
}정리 :
다이나믹 프로그래밍은 순환식의 값을 계산하는 기법이다.
다이나믹 프로그래밍 : 메모이제이션 or 바텀-업 방식 둘다 사용 가능
메모이제이션은 탑-다운 방식,
바텀-업 방식은 recursion에 수반되는 오버헤드가 없다.(함수 호출로 인한 수행시간 오버헤드가 존재 = 오버헤드)
행렬 경로 문제(조건 : 우측 또는 아래로만 이동할 수 있을 때)
L[i,j] : (1,1)에서 (i,j)까지 이르는 최소합
아래는 순환식
m // 다음 도착 지점 // base case
L[i-1, j] + m // base case
L[i, j-1] + m // base case
min(L[i-1, j] + m, L[i, j-1] + m) // general case
L[i,j] = min(L[i-1, j] + m, L[i, j-1] + m);
i == 1, j == 1 // 외길
중요 ) general case와 base case를 완전하게 세우는 것이 중요.
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, j-1), mat(i-1, j)) + m[i][j]
}위 코드는 중복된 계산이 많다.(재귀 호출은 기본적으로 중복 호출이 많을 가능성이 높아보인다.)
메모이제이션하여 개선
int mat(int i, int j){
if(L[i][j] > -1) return L[i][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 {
L[i][j] = Math.min(mat(i, j-1), mat(i-1, j)) + m[i][j]
return L[i][j];
}
}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[1][1];
else if(i==1) mat(i, j-1) + m[i][j];
else if(j==1) mat(i-1, j + m[i][j];
else {
L[i][j] = Math.min(mat(i, j-1), mat(i-1, j)) + m[i][j];
}
}
}
}경로 구하기
// initialise 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] = 'start';
}else {
if(L[i-1][j] < L[i][j-1]){
L[i][j] = m[i][j] + L[i-1][j];
p[i][j] = 'up';
}else{
L[i][j] = m[i][j] + L[i][j-1];
p[i][j] = 'left';
}
}
}
}
}
void printPath(){
int i = n, j= n;
while(P[i][j] != 'start'){ // i != 1 && j != 1
print(i + " " + j);
if(P[i][j] == 'left') j = j-1;
else i = i-1;
}
print(i + " " + j);
}동적계획법
일반적으로 최적화 문제(최솟값, 최댓값) 혹은 카운팅 문제에 적용
주어진 문제에 대한 순환식을 정의한다.
순환식을 메모이제이션 또는 바텀업으로 푼다.
순환식
subproblem들을 풀어서 원래 문제를 푸는 방식, 그런 의미에서 분할정복법과 공통성이 있음
분할 정복법은 subproblem 들이 서로 연관이 없다(disjoint 하다)
반면에 동적계획법은 subProblem들이 서로 연관되어 있다.
동적 계획법은 Optimal Substructure -> 순환식 -> 결과
Optiaml Substructure는 최적의해 내부에 포함된 해들은 최적의 해여야 한다.
ex ) 최단 경로에서 a -> c 까지 가는 최단 경로를 구할 때 그 사이에 있는 b 좌표까지 이동한 경로가 최단 경로여야 한다.
따라서, a -> b는 최단 경로여야하고, b -> c 도 최단 경로여야 한다.
예외 상황이 존재한다.
최장 경로를 구할 때 1, 2, 3, 4 네개의 좌표가 존재한다고 가정하고, 1 -> 4까지 이동하는 최장 경로는 당연히 1 -> 2 -> 3 -> 4가 될 것이다.
하지만 1 -> 3까지 이동하는 최장경로가 1 -> 2 -> 3이라는 보장은 없다.
1 -> 4 -> 2 -> 3이 될 수도 있는 것이다.
즉 최적해 A를 구하고 최적해 A에서 B로 이동했을 떄 또 최적해가 주어지고, 마지막 정점인 C로 이동할 때까지 최적해가 유지된다면 그건 Optimal Substructure이다.
이 part어렵다.... 행렬의 곱셈.... 부분 난이도 어렵다...
행렬의 곱셈 (참고 : A 행렬 q x k과 B 행렬 q x r 행렬이 있을 때 서로 곱하기 위해선 A 행과 B 열의 크기가 같아야 한다. 즉, q = r을 성립해야 한다.)
순환식 : m[i,j] : A.iA.i+1...Aj를 곱하는 최소곱셈 횟수
m[i,j] 의 최적의 해는 0 또는
(i<=k<=j-1)일 때
min(m[i,k] + m[k+1,j] + p.i-1 p.i-1 p.k * p.j)이다
(행렬의 곱셈 법칙에 의해 pqr인 것처럼 p.i-1p.kp.j가 된다.)
대각선으로 뻗어나가는 계산 순서
int matrixChain(int n)
{
for(int i = 1; i <= n; i++){
m[i][i] = 0;
}
for(int r = 1; r <= n-1; r++){ // n-1개
for(int i = 1; i <= n-r; r++){ // 각 대각선의 값의 개수
int j = i + r;
m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
for(int k = i+1; k <= j-1; k++){
if(m[i][j] > m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])
m[i][j] = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
}
}
}
return m[1][n];
}시간복잡도 : O(n^3)
learning 출처 : https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/dashboard
