ch 3. 분할 정복법 (divide-and-conquer)

• 분할 정복법 (divide-and-conquer)
• 분할 => 해결하기 쉽도록, 문제를 여러개의 작은 부분으로 나눔
• 정복 => 작게 나뉘어진 문제를 해결
• 통합 => 필요에 따라 해결된 답을 모음
• ==>> 하향식(Top-down) 접근법
  
  
• Binary search using recursive method (이분검색, 재귀알고리즘)
• 문제 : 크기가 n인 정렬된 배열에서 x가 있는지 결정하기
• 입력 : 비내림차순으로 정렬된 배열(1~n), 찾고자하는 항목(x)
• 출력 : x가 존재할 경우 해당 위치, 없는 경우 0




---


#include <stdio.h>




int goal;

int array[10]={1,2,3,4,5,6,7,8,9,10};




int location(int start, int end)

{

        int mid;

        if(start > end)

                return 0;

        else

        {   

                mid = (start+end)/2;

                if ( goal == array[mid])

                        return mid;

                else if( goal < array[mid])

                        return location(start, mid-1);

                else

                        return location(mid+1, end);

        }   




}

int main(void)

{

        int input, result;




        printf("\nWhat do you want? : ");

        scanf("%d", &input);

        goal = input;




        result = location (0, 9); 




        printf("\nyour goal was %d and our result is %d (index:%d)\n\n",input,array[result],result);




        return 0;

            

}


---

• 합병 정렬 (Merge Sort)
• 문제 : n개의 정수를 비내림차 정렬
• 입력: 크기가 n인 배열
• 출력: 비내림차순으로 정렬된 배열
  
  
• 공간복잡도 향상 시킨 알고리즘 (after. 기억공간 사용 X)




---




void mergesort2 (index low, index high) { 

        index mid;

        if (low < high) {

                mid = (low + high) / 2; 

                mergesort2(low, mid); 

                mergesort2(mid+1, high); 

                merge2(low, mid, high);

        }                            

}

...

mergesort2(1, n); 

...




---

void merge2(index low, index mid, index high) {

        index i, j, k; keytype U[low..high]; // 합병하는데 필요한 지역 배열 i = low; j = mid + 1; k = low;

        while (i <= mid && j <= high) {

                if (S[i] < S[j]) { 

                        U[k] = S[i];

                        i++; 

                } else {

                        U[k] = S[j];

                        j++; 

                }

                k++; 

        }

        if (i > mid)    

                copy S[j] through S[high] to U[k] through U[high];

        else            

                copy S[i] through S[mid] to U[k] through U[high];

        copy U[low] through U[high] to S[low] through S[high];

}




---

#include <stdio.h>




int array[10] = {10,5,2,9,7,6,4,1,8,3};

int result[10]={0};

void merge2(int low, int mid, int high) {

        int i, j, k, loop1, loop2; 

        i = low; j = mid + 1; k = low;  

        while (i <= mid && j <= high) {

                if (array[i] < array[j]) { 

                        result[k] = array[i];

                        i++; 

                } else {

                        result[k] = array[j];

                        j++; 

                }   

                k++; 

        }   




        if (i > mid)

        {   

                for(loop1 = j, loop2 = k ; loop1 <= high ; loop1++, loop2++ )

                        result[loop2]=array[loop1];

        }   

        else

        {   

                for(loop1 = i, loop2 = k ; loop1 <= mid ; loop1++, loop2++ )

                        result[loop2]=array[loop1];

        }   

        for(loop1 = low ; loop1 <= high ; loop1++ )

                array[loop1] = result[loop1];

}




void mergesort2 (int low, int high) { 

        int mid;

        if (low < high) {

                mid = (low + high) / 2;  

                mergesort2(low, mid); 

                mergesort2(mid+1, high); 

                merge2(low, mid, high);

        }   

}




int main(void)

{

        int i;




        printf("Original Array : ");

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

                printf("%d ",array[i]);




        mergesort2(0, 9); 




        printf("\nSorted Array :   ");

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

                printf("%d ",result[i]);

        printf("\n");

        return 0;

}




---




• 합병정렬 알고리즘 (before)




---


void mergesort (int n, keytype S[]) { 

        const int h = n / 2, m = n - h;  

        keytype U[1..h], V[1..m];




        if (n > 1) {

                copy S[1] through S[h] to U[1] through U[h]; 

                copy S[h+1] through S[n] to V[1] through V[m]; 

                mergesort(h,U);

                mergesort(m,V);
    merge(h,m,U,V,S);

        }   

}


---

void merge(int h, int m, const keytype U[], const keytype V[], keytype S[]) {

        index i, j, k;

        i = 1; j = 1; k = 1;

        while (i <= h && j <= m) {




                if (U[i] < V[j]) { 

                        S[k] = U[i];

                        i++; 

                } else {

                        S[k] = V[j];

                        j++; 

                }

                k++; 

        }

        if (i > h)      

                copy V[j] through V[m] to S[k] through S[h+m]; 

        else            

                copy U[i] through U[h] to S[k] through S[h+m]; 

}

• 빠른 정렬 (퀵소트, Quick sort)
• 사실상 분할교환정렬이 더 옳은 표현
• 문제 : n개의 정수를 비내림차순으로 정렬
• 입력 : 크기가 n인 배열
• 출력 : 비내림차순으로 정렬된 배열
• 기본 알고리즘 --> 분할 + 교환
• 퀵소트 기본 알고리즘

------
void quicksort (index low, index high) { 
 index pivotpoint;
 if (high > low) { 
  partition(low,high,pivotpoint); 
  quicksort(low,pivotpoint-1); 
  quicksort(pivotpoint+1,high);
  }
}

• 분할
• 문제 : 배열을 2개로 쪼갬
• 입력 : 인덱스 low, high. 인덱스 low~high에 해당하는 부분배열
• 출력 : 부분배열의 기준점(피봇, pivot), pivot point
  


-----
void partition (index low, index high, index& pivotpoint) {
index i, j;
keytype pivotitem;
pivotitem = S[low]; //pivotitem을 위한 첫번째 항목을 고른다 
j = low;


for(i = low + 1; i <= high; i++)
  if (S[i] < pivotitem) {
    j++;
    exchange S[i] and S[j];
   }
   pivotpoint = j;
exchange S[low] and S[pivotpoint]; // pivotitem 값을 pivotpoint에 넣는다
}

-----

Quick Sort example

#include <stdio.h>

int array[10] = {10,5,2,9,7,6,4,1,8,3};

void partition(int low, int high, int* pivotpoint)

{

        int i, j, pivotitem,swap;

        pivotitem = array[low];

        j = low;

        for(i = low + 1; i <= high; i++)

        {   

                if (array[i] < pivotitem) { 

                        j++;

                        swap=array[j];

                        array[j] = array[i];

                        array[i] = swap;

                }   

        }   

        *pivotpoint=j;

        swap=array[low];

        array[low] = array[j];

        array[j] = swap;

}

void quick_sort(int low, int high)

{

        int pivotpoint;

        if( high > low )

        {   

                partition(low, high, &pivotpoint);

                quick_sort(low, pivotpoint-1);

                quick_sort(pivotpoint+1, high);

        }   

}

int main(void)

{

        int i;

        printf("Original Array : ");

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

                printf("%d ",array[i]);

        printf("\n");

        quick_sort(0, 9); 

        printf("\nSorted Array :   ");

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

                printf("%d ",array[i]);

        printf("\n");

        return 0;

}

• 행렬 곱셈 (Matrix multiplication)
• 문제 : n * n 크기의 행렬의 곱 구하기기
• 입력 : n*n 크기의 행렬 A, B
• 출력 : 행렬 곱의 결과 행렬 C
• 쉬트라센 방법 : https://ko.wikipedia.org/wiki/%EC%8A%88%ED%8A%B8%EB%9D%BC%EC%84%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• 큰 정수의 표현
• 배열 요소마다 각 자릿수 표현
• 큰 정수의 덧셈, 뺄셈, 곱셈

• 임계값 결정하기 (determining threshold)
• 합병 정렬 원리 이용