알고리즘설계와분석 (CSE3081-2반 ) 중간고사 (2013년 10월24일 ( 목 ) 오전 10시30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성수강학년 : 2학년문제 : 총 8쪽 12문제 ========================================= < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고반드시답을쓰는칸에답안지의어느쪽의뒷면에답을기술하였는지명시할것. 연습지의내용은채점하지않음. ========================================= a log int i; void select(int a[], int le, int ri, int k) { // Input: a[le] to a[ri] inclusive if (ri <= le) { i = le; return; // Line (A) i = partition(a, le, ri); // takes O(ri-le+1) time if (i > k) select(a, le, i-1, k); if (i < k) select(a, i+1, ri, k); select(a, 0, n-1, k-1) n k 1
Line (A) å j a k= i k #define max(a, b) (((a) >= (b))? (a) : (b)) long MaxSubseqSum0(int A[], unsigned Left, unsigned Right) { int Center, i; long MaxSum, MaxLeft, MaxRight, MaxCenter; long MaxCenterL, MaxCenterR, ThisSum; if (Left == Right) { if (A[Left] > 0) return A[Left]; else return 0; Center = (Left + Right) / 2; MaxLeft = MaxSubseqSum(A, Left, Center); MaxRight = MaxSubseqSum(A, Center+1, Right); MaxCenter = (B) ; MaxSum = max(max(maxleft, MaxRight), MaxCenter); return MaxSum; long MaxSubseqSum1(int A[], unsigned n) { long MaxSum, ThisSum; unsigned k; MaxSum = ThisSum = 0; for (k = 0; k < n; k++) { if (ThisSum + A[k] > 0) ThisSum = (C) ; else ThisSum = 0; if (MaxSum < ThisSum) MaxSum = ThisSum; return MaxSum; (A) (B) (C) printf("the right index is %d.\n", right); MaxCenterL = 0; ThisSum = 0; for (i = Center; i >= Left; i--) { ThisSum = (A) ; MaxCenterL = max(maxcenterl, ThisSum); MaxCenterR = 0; ThisSum = 0; for (i = Center+1; i <= Right; i++) { ThisSum = (A) ; MaxCenterR = max(maxcenterr, ThisSum); S // Find the k-th smallest elements of S. procedure SELECT(k, S) { if S < 50 { sort S; return k-th smallest element in S; else { divide S into sequences of 5 elements each with up to four leftover elements; sort each 5-element sequence; 2
let M be the sequence of medians of the 5-element sets; m = SELECT(ceil( M /2), M); let S1, S2, and S3 be the sequences of elements in S less than, equal to, and greater than m, respectively; if S1 >= k { return SELECT(k, S1); else if ( S1 + S2 >= k) { return m; else { return SELECT( (A) ); (A) (B) (B) m m = median of three randomly selected elements of S; max 3
if (X[i]!= X[j]) { L[i][j] = max( (A), (B) ); else { // X[i] == X[j] if (j == i+1) L[i][j] = (C) ; else L[i][j] = (D) + 2; void sort(int data[], int n) { // Sort the n elements in the array data[]. my_sort(data, 0, n-1); // Line (A) void my_sort(int array[], int left, int right) { int what, l_hold, r_hold; // Line (B) l_hold = left; r_hold = right; what = array[left]; // Line (C) while (left < right) { while ((array[right] >= what) && (left < right)) right--; if (left!= right) { array[left] = array[right]; left++; while ((array[left] <= what) && (left < right)) left++; if (left!= right) { array[right] = array[left]; right--; array[left] = what; what = left; left = l_hold; right = r_hold; // Line (D) if (left < what) my_sort(array, left, what-1); if (right > what) my_sort(array, (E) ); Line (C) Line (D) (E) sort() sort() Line (B) if (right-left <= 5) return; Line (A) your_sort() your_sort(data, 0, n-1); 4
#define less(a, B) ((A) < (B)) #define exch(a, B) { int t = A; A = B; B = t; #define compexch(a, B) if (less(b, A)) exch(a, B) void your_sort(int a[], int l, int r) { int i; for (i = l+1; i <= r; i++) compexch(a[l], a[i]); for (i = l+2; i <= r; i++) { int j = i; int v = a[i]; while (less(v, a[j-1])) { a[j] = a[j-1]; (F) ; a[j] = v; your_sort() (F) (A) (B) (C) #include <stdio.h> #define N 5 #define INFTY 100000 int c[n+1][n+2] = { -1, -1, -1, -1, -1, -1, -1, -1, 7, 3, 5, 6, 1, -1, -1, 2, 6, 7, 0, 2, -1, -1, 3, 5, 7, 8, 2, -1, -1, 7, 6, 1, 1, 4, -1, -1, 6, 7, 4, 7, 8, -1 ; int p[n+1][n+2], q[n+1][n+2]; int min3(int a, int b, int c) { // Return the minimum of a, b and c. void ComputeCBCosts(int n) { int i, j, min; for (i = 1; i <= n; i++) q[1][i] = c[1][i]; for (i = 1; i <= n; i++) { q[i][0] = INFTY; q[i][n+1] = INFTY; for (i = 2; i <= n; i++) { for (j = 1; j <= n; j++) { min = min3(q[i-1][j-1], (B) ); q[i][j] = min + (C) ; if (min == q[i-1][j-1]) p[i][j] = -1; else if (min == q[i-1][j]) p[i][j] = 0; else p[i][j] = 1; void PrintShortestPath(int n, int imin) { printf(" (%d, %d) <-", n, imin); if (n == 2) printf(" (%d, %d) \n", 1, imin + (D) ); else PrintShortestPath(n-1, imin + (D) ); void ComputeCBShortestPath(int n) { int i, imin, min; ComputeCBCosts(n); imin = 1; min = q[n][1]; for (i = 2; i <= n; i++) { if (q[n][i] < min) { imin = i; min = q[n][i]; 5
printf("*** The cost of the shortest path is %d. \n", q[n][imin]); PrintShortestPath(n, imin); void main(void) { ComputeCBShortestPath(N); (D) PrintShortestPath(n, imin) ( 문제끝 ) 6
1 // Starting from the code in http://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/ 2 // Modified for Sogang CSE3081-2 3 4 5 /* Solving the Box Stacking problem using Dynamic Programming */ 6 #include<stdio.h> 7 #include<stdlib.h> 8 9 #define min(x,y) ((x) < (y))? (x) : (y) 10 #define max(x,y) ((x) > (y))? (x) : (y) 11 12 typedef struct _Box { 13 int h, w, d; // d >= w 14 Box; 15 16 int compare_area (const void *a, const void * b) { 17 return ( (*(Box *)b).d * (*(Box *)b).w ) - 18 ( (*(Box *)a).d * (*(Box *)a).w ); 19 20 21 void BoxStacking( Box boxes[], int n ) { 22 Box *allboxes; 23 int *H, *below, tmax, tmaxi, cur, next; 24 25 allboxes = (Box *) malloc(sizeof(box)*3*n); 26 H = (int *) malloc(sizeof(int)*3*n); 27 below = (int *) malloc(sizeof(int)*3*n); 28 29 printf("the input boxes are\n"); 30 for (int i = 0; i < n; i++ ) 31 printf("%d x %d x %d\n", boxes[i].h, boxes[i].w, boxes[i].d); 32 33 34 next = 0; 35 for (int i = 0; i < n; i++) { 36 allboxes[next++] = boxes[i]; 37 38 allboxes[next].h = boxes[i].w; 39 allboxes[next].d = max(boxes[i].h, boxes[i].d); 40 allboxes[next++].w = min(boxes[i].h, boxes[i].d); 41 42 allboxes[next].h = boxes[i].d; 43 allboxes[next].d = max(boxes[i].h, boxes[i].w); 44 allboxes[next++].w = min(boxes[i].h, boxes[i].w); 45 46 47 qsort(allboxes, 3*n, sizeof(allboxes[0]), compare_area); 48 49 printf("\nthe all sorted rotations of the input boxes are\n"); 50 for (int i = 0; i < 3*n; i++ ) 51 printf("%d x %d x %d\n", allboxes[i].h, allboxes[i].w, allboxes[i].d); 52 printf("\n"); 53 54 55 for (int i = 0; i < 3*n; i++) { 56 H[i] = allboxes[i].h; below[i] = i; 57 58 59 for (int i = 1; i < 3*n; i++ ) 60 for (int j = 0; j < i; j++ ) 61 if ( allboxes[i].w < allboxes[j].w && allboxes[i].d < allboxes[j].d 62 && H[i] < H[j] + allboxes[i].h ) { 63 H[i] = H[j] + allboxes[i].h; 64 below[i] = j; 65 66 67 tmax = tmaxi = -1; 68 for ( int i = 0; i < 3*n; i++ ) 69 if ( tmax < H[i] ) { 70 tmax = H[i]; tmaxi = i; 71
72 73 printf("the maximum possible height is %d.\n\n", tmax); 74 printf("the stacking order from top to bottom is \n"); 75 76 next = tmaxi; 77 do { 78 cur = next; 79 printf("** %d x %d x %d\n", allboxes[cur].h, allboxes[cur].d, allboxes[cur].w); 80 while ((next = below[cur])!= cur); 81 printf("\n"); 82 83 84 85 void main(void) { 86 int n; 87 Box boxes[] = { {4, 6, 7, {1, 2, 3, {4, 5, 6, {10, 12, 32, {3, 4, 5 ; 88 89 n = sizeof(boxes)/sizeof(boxes[0]); 90 BoxStacking(boxes, n); 91 92 93