알고리즘 설계 - 분할 정복

분할 정복(Divide and Conquer)은 큰 문제를 더 작은 하위 문제로 나누고, 이러한 하위 문제를 해결하여 원래의 문제를 해결하는 방식이다. 분할 정복 방법은 주로 재귀적으로 구현되며 이를 하향식 접근방법이라고 한다.

분할 정복 알고리즘은 일반적으로 다음 세 단계를 거친다.

1. **분할(Divide)**: 원래의 문제를 더 작은 하위 문제로 분할.

2. **정복(Conquer)**: 각 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작아서 직접적으로 해결할 수 있을 때까지 이 과정을 반복.

3. **결합(Combine)**: 하위 문제의 해결책을 결합하여 원래의 문제를 해결.

---

분할 정복법에 해당하는 알고리즘들

: 이진 검색, quick sort, 행렬 곱셈(strassen 방법)

 

이진 검색

index location(index low, index high){
	index mid;
    if(low>high) return -1; //검색실패
    else{
    	mid = (low + high)/2
        if (x==S[mid])
        	return mid;
        else if(x<S[mid])
        	return location(low,mid-1); //작은쪽 재귀
        else
        	return location(mid+1, high);//큰쪽 재귀
    }

}
..
locationout = location(0,n-1);

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


}

index partition(index low, index high){
	index i,j,pivotpoint;
    keytype pibotitem;
    pivotitem=S[low]; //첫번째항목이 피벗
    j=low;
    for(i=low+1;i<=high;i++)
    	if(S[i]<pivotitem) {j++; exch(S[i],S[j]);}
    pivotpoint=j;
    
    exch(S[low],S[pivotpoint]);
    return pivotpoint;

}

j가 피봇의 위치를 트래킹하면서, 피봇보다 작은 값을 만날때마다 피봇의 위치j의 아이템과 해당 값을 바꿔치기한다.

---

분할정복법을 사용할 수 없는 경우

: 크기가 n인 입력이 2개 이상의 조각으로 분할되며, 분할된 부분들의 크기가 거의 n에 가깝게 되는 경우

 

Tn = Tn-1 + Tn-2 + 1 ..