분할 정복 기법

분할 정복 기법

• 설계 전략

  • 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
  • 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
  • 통합(Combine) : (필요하다면)해결된 해답을 모으기

  

• 장단점

장점 : 문제를 나눔으로써 어려운 문제를 해결할 수 있다는 엄청나게 중요한 장점이 있다. 그리고 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며, 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.

단점: 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점

반복(Iterative) 알고리즘 : O(n)

N2 = N x N
N3 = N x N x N
...
Nn = N x N x N ... N

분할 정복 기반의 알고리즘 : O(log2n)

N8 = N4 x N4 = ((N2)2)2
Nn = N$\frac{n-1}{2}$ x N$\frac{n-1}{2}$ x N = (N$\frac{n-1}{2}$)2 x N

이진 검색

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

  • 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함

• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

• 검색 과정

1. 자료의 중앙에 있는 원소를 고르기
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교
3. 중앙 원소의 값과 찾고자 하는 목표 값이 일치하면 탐색 끝
4. 목표 값이 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색 수행, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행
5. 찾고자 하는 값을 찾을 때 까지 위 과정을 반복

• 알고리즘 : 반복 구조

binarySearch(arr[], n, answer)
	start = 0;
    end = n-1;
    
    while(start<=end){
    	mid = (start+end)/2
        if(arr[mid] == key)
        	return mid;
        else if(arr[mid] < key)
        	start = mid+1;
        else if(arr[mid] > key)
        	end = mid-1;
            
    }

• 알고리즘 : 재귀구조

binarySearch(arr[], start, end, answer)
	if(start>end)
    	return -1;
    else{
    	mid = (start + end) / 2;
        mid = (start+end)/2
        if(arr[mid] == key)
        	return mid;
        else if(arr[mid] < key)
        	return binarySearch(arr[], mid+1, end, answer);
        else if(arr[mid] > key)
        	return binarySearch(arr[], start, mid -1, answer);

• java.util.Arrays.binarySearch
  • 이진탐색 API
  • int binarySearch(int[] a, int key)
  • int binarySearch(int[] a, int fromIndex, int toIndex, int key)