[알고리즘] ep5-3++) 분할통치법 vs DP

문제) 여행의 최소비용을 구하는 알고리즘을 작성하라.

airtelDC(분할통치 버전)와 airtelDP(동적프로그래밍 버전)를 구현하고 실행시간을 비교

 

프로그램 요구사항:

1)  각 해결버전의 정방향, 역방향 버전 가운데 자유롭게 하나를 선택하여 구현하라.

2)  출력예시: 최종적으로 다음과 같이 인쇄되어야 한다.

 

※ 참고

1) 아래는 MAX = 30인 경우의 인쇄결과임.

2) X.XXXXXXXX는 cputime in milliseconds.

 

 

주의:

1. 반드시 아래 가이드라인의 main 함수 내용과 동일하게 실행하고 출력을 구하라.
2. n = 6로 한 테스트실행 결과가 수작업실행 결과와 일치하는지 확인한 후 n = MAX로 한 본실행을 시도할 것.
3. 경로가 아닌 최소비용만을 요구하는 문제이므로, 만약 최소비용 경로가 두 개 이상이라 하더라도 그중 아무거나 출력하면 된다.
4. 어떤 호출(들)에 대한 계산이 너무 빨라 cputime = 0으로 나타나는 것은 허용하지만, n = MAX로 한 본실행 단계에서, airtelDC 호출에 대한 계산이 너무 느리거나 너무 빨라 airtelDP의 실행 결과와 비교하기에 적당한 cputime을 구하기 어려운 경우에 한하여, 전역변수 MAX 값 30을 정확히 절반(즉, 15)으로 줄이거나 두 배(즉, 60)로 늘려 실행하여 제출해도 좋다(15, 30, 60 이외 다른 수 사용은 불가!).

 

 

<주요 함수 의사코드>

 

A배열: 거리에 따른 항공요금 / B배열: 숙박요금

n = 6일 때, mincost = 10

 

 

DC (Divide-Conquer) - 비효율적

도착도시 d에 대해, 도시 k를 경유할 때마다 총비용 cost를 계산하여 그 가운데 최소값을 찾는다

총 O(2^n) 시간 소요

(정방향)

 

분할통치법은 과도한 중복호출로 인해 효율이 너무 떨어진다

 

 

 

반면에, 동적 프로그래밍에서는 크기 n의 배열 res을 사용하여 중간 계산값들을 저장하여 사용함으로써 한 번 계산한 배열원소에 대한 중복계산을 방지한다

DP(Dynamic Programming) - 효율적

도착도시 d에 대해, 도시 k를 경유할 때마다 총비용 cost를 계산하여 그 가운데 최소값을 찾아 res[d]에 저장

총 O(n) 공간, O(n^2) 시간 소요

(정방향)

 

res[d]: 도시 0에서 d로 가는 mincost

res[n - 1]: 도시 0에서 n - 1로 가는 mincost

 

 

 

 

(전체코드) - Windows에서만 실행 가능

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <time.h>

#define MAX 60

int g_H[MAX]; // 숙박요금
int g_A[MAX]; // 항공요금

int rAirtelDC(int s, int d);
int airtelDP(int n, int s, int d);
int getMin(int x, int y);

int main() {
   int test[3][2] = { {0, 4}, {2, 5}, {2, 4} }; // test (s, d)
   int n; // 도시의 개수
   int s, d; // src city, dest city
   int minCost;
   LARGE_INTEGER ticksPerSec;
   LARGE_INTEGER start, end, diff;
   srand(time(NULL));
   QueryPerformanceFrequency(&ticksPerSec);

   // 숙박요금 초기화
   g_H[0] = 0;
   g_H[1] = 5;
   for (int i = 2; i < MAX; i++) {
      g_H[i] = (g_H[i - 1] + i) % 9 + 1;
   }

   // 항공요금 초기화
   g_A[0] = 0;
   g_A[1] = 1;
   for (int i = 2; i < MAX; i++) {
      g_A[i] = g_A[i - 1] + g_A[i - 1] % 5 + 3;
   }

   // 결과 출력 형식 헤더
   printf("%-3c %-3c %-3c %-8s %-8s %-10s\n", 'n', 's', 'd', "mincost", "version", "cputime");

   // 테스트실행
   n = 6;
   for (int i = 0; i < 3; i++) {
      s = test[i][0];
      d = test[i][1];

      // DC(Divide and Conquer)
      QueryPerformanceCounter(&start);
      minCost = rAirtelDC(s, d);
      QueryPerformanceCounter(&end);
      diff.QuadPart = end.QuadPart - start.QuadPart;
      printf("%-3d %-3d %-3d %-8d %-8s %-10f\n", n, s, d, minCost, "DC", ((double)diff.QuadPart / ((double)ticksPerSec.QuadPart) * 1000));

      // DP(Dynamic Programming)
      QueryPerformanceCounter(&start);
      minCost = airtelDP(n, s, d);
      QueryPerformanceCounter(&end);
      diff.QuadPart = end.QuadPart - start.QuadPart;
      printf("%-3d %-3d %-3d %-8d %-8s %-10f\n", n, s, d, minCost, "DP", ((double)diff.QuadPart / ((double)ticksPerSec.QuadPart) * 1000));
   }

   // 본실행
   n = MAX / 2;
   s = 1;
   d = n - 2;

   // DC(Divide and Conquer)
   QueryPerformanceCounter(&start);
   minCost = rAirtelDC(s, d);
   QueryPerformanceCounter(&end);
   diff.QuadPart = end.QuadPart - start.QuadPart;
   printf("%-3d %-3d %-3d %-8d %-8s %-10f\n", n, s, d, minCost, "DC", ((double)diff.QuadPart / ((double)ticksPerSec.QuadPart) * 1000));

   // DP(Dynamic Programming)
   QueryPerformanceCounter(&start);
   minCost = airtelDP(n, s, d);
   QueryPerformanceCounter(&end);
   diff.QuadPart = end.QuadPart - start.QuadPart;
   printf("%-3d %-3d %-3d %-8d %-8s %-10f\n", n, s, d, minCost, "DP", ((double)diff.QuadPart / ((double)ticksPerSec.QuadPart) * 1000));

   return 0;
}

int rAirtelDC(int s, int d) { // 정방향 분할통치법: O(2^n)
   if (s == d) {
      return 0;
   }

   int minCost = 2147483647;
   int cost;
   for (int k = s; k < d; k++) { // 각 도시를 경유지로 설정 (k는 경유지를 의미)
      // cost = 출발 도시에서 경유 도시까지의 비용 + 경유 도시에서의 숙박요금 + k에서 d로 가는 항공요금
      cost = rAirtelDC(s, k) + g_H[k] + g_A[d - k];
      if (cost < minCost) {
         minCost = cost;
      }
   }
   return minCost;
}

int airtelDP(int n, int s, int d) { // 동적 프로그래밍 - 정방향: O(n^2)
   int* res = (int*)malloc(n * sizeof(int)); // 최소 비용을 저장할 배열
   res[s] = 0; // 출발 도시는 비용 0
   int cost;
   for (int i = s + 1; i <= d; i++) { // 출발 도시(s) 다음부터 도착 도시(d)까지
      res[i] = 2147483647;
      for (int k = s; k < i; k++) { // 각 도시를 경유지로 설정 (k는 출발 도시에서 도착 도시 i로 가는 경로에서 경유하는 도시를 의미)
         // cost = 출발 도시에서 경유 도시 k까지의 최소 비용 + 경유 도시에서의 숙박요금 + 경유 도시 k에서 도착 도시 i로 가는 항공 요금
         cost = res[k] + g_H[k] + g_A[i - k];
         res[i] = getMin(res[i], cost); // 최소 비용 갱신
      }
   }
   int ans = res[d]; // 도시 s에서 d로 가는 minCost
   free(res);
   return ans;
}

int getMin(int x, int y) {
   return (x < y) ? x : y;
}

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님)