알고리즘 - 분할정복

알고리즘 - 분할정복

 

1) 분할 : 해결하기 쉽도록 문제를 작은 부분으로 나눈다.

2) 정복 : 나눈 작은 문제를 “각각” 해결한다.

3) 통합 : (필요하다면) 해결된 해답을 모은다.

 

 

이러한 문제 해결 방법을(top-down)하향식 접근방법 이라고 한다.

 

 

이는 이분검색(Binary Search) 재귀 알고리즘을 이용한다.

이분검색은 O(logn)의 복잡도를 가진다. 순차검색이 O(n)이 걸리는 것을 보면 더욱 효율적인 알고리즘인 것을 알 수 있다.

 

 

이분검색의 설계전략:

1) x가 배열의 중간에 항목과 같으면 빙고 그렇지 않으면:

분할 : 배열을 나누어서 x가 중앙보다 작으면 왼쪽에 위치한 반쪽을 선택하고 그렇지 않으면 오른쪽에 위치한 배열 반쪽을 선택한다.

2) 정복 : 선택된 반쪽 배열에서 x를 찾는다.

3) 이 두 개를 반복한다.

4) (이 때)통합은 사용되지 않는다.

 

index location (index low, index high){
	index mid;

	if(low>high)
	   return 0;
	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(1,n);

 

고찰 : 위의 재귀함수의 파라미터 (S,n)과 같은 것들은 변하지 않는 값이기 때문에 낭비가 된다.

이를 꼬리 재귀호출이라고 하는데 이와 같은 알고리즘은 반복 알고리즘으로 변환하기 수월하다. 그렇다고 반드시 복잡도가 재귀보다 좋다는 것은 아니다. 반복 알고리즘이 상수적으로만 좋다는 말이다.

 

분할정복의 시간 복잡도