ch 3. 동적 프로그래밍 (dynamic programming)

• 동적 프로그래밍 (dynamic programming)
• 분할 정복법과 유사
• 문제를 더 작은 단위로 분할
• 작은 단위를 먼저 해결하고, 결과를 저장하고, 후에 결과가 필요할 때 재계산 하지 않고 결과를 찾아다 씀    
• 상향식 (Bottom Up)
• 작은 단위로 나뉘어진 것들이 상관관계가 있는 경우 적합 (Ex. 반복적 피보나치)
• 재귀적 관계식을 세워서 상향식으로 해결!

• 이항계수 구하기 (Binomial Coefficient)
• 기본공식
  
  
  
  
• 관계식으로 표현된 식
  
• 분할정복법으로 구하게 되면 재귀 호출을 수행해야함
• 동적 프로그래밍 설계 전략
• 1단계 : 재귀 관계식 정립
  2차원 배열을 만들어서 각 인덱스에 해당하는 값을 저장하여 그 다음 관계식에서 활용
• 2단계 : 상향식 방법으로 문제 해결
• 알고리즘
  

int bin2(int n, int k) { 

        index i, j;  

        int B[0..n][0..k]; 

        for(i=0; i<=n; i++) 

                for(j=0; j <= minimum(i,k); j++)


                        if  

                                (j==0 || j == i) B[i][j] = 1;
 

                        else 

                                B[i][j] = B[i-1][j-1] + B[i-1][j]; 

        return B[n][k]; 

}


• 코드 예시

#include <stdio.h>




int B[10][10]={0};




int minimum(int n, int m) {

        if (n<m) return m;

        else return n;

}

int bin2(int n, int k) { 

        int i, j;  

        for(i=0; i<=n; i++) 

                for(j=0; j <= minimum(i,k); j++)


                        if  

                                (j==0 || j == i) B[i][j] = 1;
 

                        else 

                                B[i][j] = B[i-1][j-1] + B[i-1][j]; 

        return B[n][k]; 

}




int main(void)

{

        int result;

        printf("Problem : 9 C 3\n");

        result = bin2(9, 3); 

        printf(" Result : %d\n", result);




        return 0;

}

• 개선된 알고리즘
• 2차원 배열 ==> 1차원 배열만 사용하도록 변경
• 한번 계산된 행은 다시 사용되지 않는 점을 착안하여 1차원 배열로 이용

#include <stdio.h>




int B[10]={0};




int bin2(int n, int k) { 

        int i, j;  

        for(i=0; i<=n; i++) 

                for(j=i; j >= 0; j--)


                        if  

                                (j==0 || j == i) B[j] = 1;
 

                        else 

                                B[j] = B[j-1] + B[j]; 




        return B[k]; 

}




int main(void)

{

        int result;

        printf("Problem : 9 C 3\n");

        result = bin2(9, 3); 

        printf(" Result : %d\n", result);




        return 0;

}

• 최단 경로 탐색
• Shortest Path : 한 도시에서 다른 도시로의 직항이 없을 때 가장 빠른 경로를 찾기
• 문제: 가중치 포함, 방향성 그래프에서 최단 경로 찾기
• 최적화 문제 (optimization problem)
  
  
• Bruteforce Algorithm (무작정)
• 한 정점에서 다른 정점으로의 모든 경로의 길이를 구한 뒤, 그들 중에서 최소 길이 찾기
• 동적계획식 - 자료구조 : 인접 행렬 표현
• 정점간의 거리를 이용하여 N-1 번째 노드까지의 길이와 N번째 노드 길이까지의 재귀 관계싱 정립
  
  
• Floyd's Algorithm (i)
• 문제 : 가중치 포함 그래피의 각 정점에서 다른 모든 정점까지의 최단거리 구하기
• 입력 : 가중치 포함 방향성 그래피 W, 그래프의 정점의 수 n
• 출력 : 최단 거리의 길이가 포함된 배열 D
• 알고리즘

• void floyd(int n, const number W[][], number D[][]) {          int i, j, k;         D = W;         for(k=1; k <= n; k++)                 for(i=1; i <= n; i++)                          for(j=1; j <= n; j++)                                 D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]); }

• Floyd's Algorithm (ii)
• 문제,입력 동일
• 출력 : 최단 경로의 길이가 포함된 배열 D, 그리고 다음을 만족하는 배열 P
• 최단 경로의 중간에 놓여있는 정점이 없으면 0
• 최단 경로 중간에 놓여있는 정점이 최소한 하나 있는 경우, 그 놓여있는 정점 중 가장 큰 인덱스값
• 알고리즘 개선

• void floyd2(int n, const number W[][], number D[][], index P[][]) {          index i, j, k;         for(i=1; i <= n; i++)                  for(j=1; j <= n; j++)                         P[i][j] = 0;          D = W;         for(k=1; k<= n; k++)                  for(i=1; i <= n; i++)                         for(j=1; j<=n; j++)                                 if (D[i][k] + D[k][j] < D[i][j]) {                                         P[i][j] = k;                                         D[i][j] = D[i][k] + D[k][j];                                  }        }

• 최적의 원칙 
• 어떤 문제의 입력에 대한 최적 해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적해를 항상 포함할 때, 최적의 원칙이 적용된다고 한다.
• 최적의 원칙이 적용되지 않는 예
• Longest Path (최장거리)

• Chained Matrix Multiplication (연쇄 행렬 곱셈)
• 어떤 행렬 곱셈을 먼저 수행하느냐에 따라 필요한 기본 곱셈 횟수가 달라짐
• bruteforce 방법 ; 가능한 모든 순서를 고려하고, 그 가운데서 최소 값을 택한다다
• 최소 곱셈 알고리즘
• 문제 : n개의 행렬곱에 필요한 기본 곱셈 횟수의 최소치 결정하고, 그 최소치를 구하기 위한 행렬 곱의 순서
• 입력 : 행렬의 수, 배열 D, D[i-1]*D[i]는 i 번째 행렬의 규모를 나타냄
• 출력 :
• 기본적인 곱셈의 횟수의 최소치를 나타내는 minmult;
• 최적의순서를 얻을수있는배열P,
• 여기서 P[i][j]는 행렬 i부터 j까지가 최적의 순서로 갈라지는 기점

• int minmult(int n, const int d[], index P[][]) {         index i, j, k, diagonal;         int M[1..n, 1..n];         for(i=1; i <= n; i++)                 M[i][i] = 0;         for(diagonal = 1; diagonal <= n-1; diagonal++)                 for(i=1; i <= n-diagonal; i++) {                          j = i + diagonal;                         M[i][j] = minimum(M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]);                          //i <= k <= j-1                         //P[i][j] = 최소치를 주는 k의 값                  }            return M[1][n];  }

• Optimal Binary Search Trees
• [Def] 이진 탐색 트리 (Binary Search Tree)
• 트리의 각 노드가 키 값을 갖고 있으며, 순서가 있음(정렬)
• 왼편 서브트리의 노드값(키)은 해당 트리보다 작거나 같고
• 오른편 서브트리의 노드값(키)은 해등 트리보다 크거나 같다
• [Def] 깊이(Depth) - 루트로 부터 엣지 개수. (노드의 레벨. 레벨은 0부터 시작함)
• [Def] 균형(Balanced) - 만약 모든 노드의 서브트리 간의 깊이 차이가 1 이하인 경우
• [Def] 최적(Optimal) - 키를 찾는데에 걸리는 평균 시간이 최소인 경우
  
  
• 트리 예시
  
  
  
  
• 문제 : 이진 탐색 트리에서 노드가 갖고 있는 키 값 찾기
• 입력 : 포인터 트리와 키 값
• 출력 : 해당 키 값을 갖고 있는 노드를 가리키는 포인터
• 분석
• 탐색 시간 - 키 값을 찾기위한 비교 횟수 : 깊이(해당 노드) + 1
• 최적 이진 탐색 트리 알고리즘

• void optsearchtree(int n, const float p[], float& minavg, index R[][]) {          index i, j, k, diagonal;         float A[1..n+1][0..n];         for(i=1; i<=n; i++) {                 A[i][i-1] = 0; A[i][i] = p[i];                  R[i][i] = i; R[i][i-1] = 0;           }            A[n+1][n] = 0; R[n+1][n] = 0;           for(diagonal=1; diagonal<= n-1; diagonal++)                 for(i=1; i <= n-diagonal; i++) {                         j = i + diagonal;                         A[i][j] = minimum(A[i][k-1]+A[k+1][j]) + sumof(p)m                                 //i<=k<=j                                 R[i][j] = a value of k that gave the minimum;                 }            minavg = A[1][n]; }

• 판매원 알고리즘 : 동적 프로그래밍의 나쁜 예
• 문제 : 판매원의 집에서 모든 도시를 한번씩 방문하고, 다시 집으로 돌아오는 경로 중 최단 경로로
  ==> 가중치의 합이 최소가 되도록 한다
• 동적 프로그래밍 방법 --> 재귀적 관계식으로 구현 ==> 인접 행렬로 데이터화