선형 자료구조에 보관한 자료 중에 최솟값을 찾는 방법은 많습니다. 그 중에 분할 정복 알고리즘으로 해결하는 방법을 알아봅시다.
분할 정복 알고리즘에서는 모집합을 부분 집합으로 나누는 작업을 선행합니다. 원하는 기준에 맞게 부분 집합으로 분리한 후에 부분 집합에서 원하는 결과를 구합니다. 그리고 해결한 부분을 합쳐서 다시 커다란 집합에서 원하는 결과를 구하는 과정을 반복합니다.
최솟값(최댓값) 찾기 알고리즘도 분할 정복 알고리즘으로 문제를 해결할 수 있습니다. 배열의 원소 중에 최솟값을 찾기 위해 원소 개수가 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 반환
이제 구체적으로 구현해 봅시다.
#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]);
}
}