[디딤돌 자료구조와 알고리즘 with C] 4. 분할 정복 알고리즘

4. 분할 정복 알고리즘

 분할 정복 알고리즘은 커다란 문제를 작은 문제로 나누어 작은 문제를 해결하고 이를 다시 합쳐 커다란 문제를 해결하는 알고리즘입니다.

 

 분할 정복 알고리즘은 내부적으로 재귀 알고리즘을 사용합니다. 대표적인 분할 정복 알고리즘에는 최소값(최대값) 찾기 알고리즘, 이진 탐색 알고리즘과 병합 정렬 알고리즘 등이 있습니다.

 

4.1 최소값(최대값) 찾기 알고리즘

 선형 자료구조에 보관한 자료 중에 최소값을 찾는 방법은 많습니다. 그 중에 분할 정복 알고리즘으로 해결하는 방법을 알아봅시다.

 

 분할 정복 알고리즘에서는 모집합을 부분 집합으로 나누는 작업을 선행합니다. 원하는 기준에 맞게 부분 집합으로 분리한 후에 부분 집합에서 원하는 결과를 구합니다. 그리고 해결한 부분을 합쳐서 다시 커다란 집합에서 원하는 결과를 구하는 과정을 반복합니다.

 

 최소값(최대값) 찾기 알고리즘도 분할 정복 알고리즘으로 문제를 해결할 수 있습니다. 배열의 원소 중에 최소값을 찾기 위해 원소 개수가 2보다 크면 배열의 앞 부분에서 최소값을 찾기 위해 재귀함수를 호출하고 마찬가지로 뒷 부분에서 최소값을 찾기 위해 재귀함수를 호출합니다. 그리고 배열의 앞 부분의 최소값과 뒷 부분의 최소값을 비교하여 작은 값을 반환합니다.

 

 배열의 앞 부분에서 최소값을 찾고 뒷 부분에서 최소값을 찾기 위해 배열을 분할하는 과정이 필요합니다. 그리고 두 부분의 최소값을 비교하여 작은 값을 반환하는 부분이 정복하는 과정입니다.

 

 다음은 최소값 찾기 알고리즘을 분할 정복 알고리즘으로 해결하기 위해 의사코드입니다.

 

최소값 찾기(arr:배열, asize:원소개수, compare:비교 논리)

  min_a = 최소값찾기(arr,asize/2,compare)

  min_b = 최소값찾기(arr,asize-asize/2,compare)

  min_a가 min_b보다 크면 min_a 반환

  min_b 반환 

 

 이제 구체적으로 구현해 봅시다.

최소값 찾기.zip

#include "common.h"

#include "Book.h"

typedef void *Element;

typedef int (*Compare)(Element , Element);

Element FindMin(Element *base,int asize,Compare compare)

{

 배열의 앞쪽 부분의 크기를 설정합니다.

    int ahalf  = asize/2;

 배열의 뒤쪽 부분의 크기를 설정합니다.

    int bhalf = asize - ahalf;

    Element min_a = 0;

    Element min_b = 0;

 만약 배열의 크기가 0보다 작거나 같으면 함수를 종료합니다.

    if(asize<=0){    return 0;    }

 만약 배열의 크기가 1이면 최소값은 index 0에 있는 원소입니다.

    if(asize == 1){    return base[0];    }

 배열의 앞쪽에서 최소값을 찾습니다.

    min_a = FindMin(base,ahalf,compare);

 배열의 뒤쪽에서 최소값을 찾습니다.

    min_b = FindMin(base+ahalf,bhalf,compare);

 찾은 두 값 중에 작은 값을 반환합니다.

    if(compare(min_a,min_b)>0){    return min_b;    }

    return min_a;

}

#define MAX_BOOK             10

Book *books[MAX_BOOK]={0};

 테스트는 시뮬레이션 초기화, 시뮬레이션, 시뮬레이션 정리순으로 진행합시다.

void SimulationInit();

void Simulation();

void SimulationClear();

int main()

{

    SimulationInit();

    Simulation();

    SimulationClear();

    return 0;

}

 시뮬레이션 초기화에서는 최대 도서 개수만큼의 도서를 생성합니다. 이 때 도서 제목과 저자명, 도서 번호를 랜덤하게 만드세요.

void SimulationInit()

{

    char title[MAX_TIT_LEN+1]="";

    char author[MAX_AUT_LEN+1]="";

    int i = 0;

 

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

    {

        sprintf(title,"%010d",rand());

        sprintf(author,"%010d",rand());

        books[i] = New_Book(title,author,rand());

    }

}

 

 시뮬레이션에서는 도서 목록을 보여준 후에 최소 값의 도서를 찾아 도서 정보를 출력합시다.

void ListBook(int n);

int CompareByNum(Book *book1,Book *book2);

void Simulation()

{

    Book *book = 0;

 

    printf("전체 도서 목록\n");

    ListBook(MAX_BOOK);

    book = (Book *)FindMin(books,MAX_BOOK,CompareByNum);

    printf("도서 번호가 가장 작은 도서\n");

    Book_View(book);

}

 

 도서 번호로 비교하는 함수를 정의합시다.

int CompareByNum(Book *book1,Book *book2)

{

    return Book_CompareNum(book1,book2->num);

}

 

 도서 목록을 출력하는 함수를 정의합시다.

void ListBook(int n)

{

    int i = 0;

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

    {

        Book_View(books[i]);

    }

}

 시뮬레이션 정리하는 함수에서는 사용한 도서 개체를 소멸합니다.

void SimulationClear()

{

    int i = 0;

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

    {

        Delete_Book(books[i]);

    }

}

 

//Program.c

#include "common.h"

#include "Book.h"

typedef void *Element;

typedef int (*Compare)(Element , Element);              

 

Element FindMin(Element *base,int asize,Compare compare)

{

    int ahalf  = asize/2;

    int bhalf = asize - ahalf;

    Element min_a = 0;

    Element min_b = 0;

 

    if(asize<=0)

    {

        return 0;

    }

    if(asize == 1)

    {

        return base[0];

    }

    min_a = FindMin(base,ahalf,compare);

    min_b = FindMin(base+ahalf,bhalf,compare);

    if(compare(min_a,min_b)>0)

    {

        return min_b;

    }

    return min_a;

}

 

#define MAX_BOOK             10

Book *books[MAX_BOOK]={0};

void SimulationInit();

void Simulation();

void SimulationClear();

int main()

{

    SimulationInit();

    Simulation();  

    SimulationClear();

    return 0;

}

 

void SimulationInit()

{

    char title[MAX_TIT_LEN+1]="";

    char author[MAX_AUT_LEN+1]="";

    int i = 0;

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

    {

        sprintf(title,"%010d",rand());

        sprintf(author,"%010d",rand());

        books[i] = New_Book(title,author,rand());

    }

}

void ListBook(int n);

int CompareByNum(Book *book1,Book *book2);

void Simulation()

{           

    Book *book = 0;

    printf("전체 도서 목록\n");

    ListBook(MAX_BOOK);

    book = (Book *)FindMin(books,MAX_BOOK,CompareByNum);

    printf("도서 번호가 가장 작은 도서\n");

    Book_View(book);

 

}

int CompareByNum(Book *book1,Book *book2)

{

    return Book_CompareNum(book1,book2->num);

}

void ListBook(int n)

{

    int i = 0;

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

    {

        Book_View(books[i]);

    }

}

 

void SimulationClear()

{

    int i = 0;

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

    {

        Delete_Book(books[i]);

    }

}