Divide and Conquer (분할정복법)

1. Divide and Conquer

문제를 여러 개의 작은 부분으로 나누어 나눈 작은 문제를 각각 해결하고, 이를 합쳐 원래의 문제를 해결하는 기법을 말한다.

2. Binary Search (이진 탐색)

정렬된 배열에서 x를 찾기 위해 사용한다.

배열을 반으로 나누어 x가 중앙에 위치한 항목보다 작다면 배열의 왼쪽 절반을 선택하고 크다면 배열의 오른쪽 절반을 선택한다.

선택한 절반 배열에서 x를 탐색한다.

W(n) = O(logn)

int binarySearch(int[] arr, int x, int low, int high){
    if(low > high) 
        return -1;
    
    int mid = (low + high) / 2;
 
    if (x < arr[mid]) 
        return binarySearch(arr, x, low, mid-1);
    else if (x > arr[mid])
        return binarySearch(arr, x, mid+1, high); 
    else
        return mid;
}

3. Mergesort (합병정렬)

배열을 절반씩 나누어 각각을 정렬한 다음 이 둘을 합하여 다시 정렬한다.

병합 대상이 되는 배열을 임시 배열에 복사하고 왼쪽 절반의 시작지점과 오른쪽 절반의 시작 지점을 찾는다.

임시 배열을 순회하면서 두 배열에서 더 작은 값을 꺼내 원래 배열에 넣는다.

두 배열 중 한 배열에 대한 순회가 끝난 경우에는 다른 배열의 남은 부분을 원래 배열에 모두 넣고 끝낸다.

W(n) = O(nlogn)

void mergeSort(int[] arr) {
    int[] tmp = new int[arr.length];
      mergeSort(arr, tmp, 0, arr.length - 1);
}
 
void mergeSort(int[] arr, int[] tmp, int low, int high){
    if(low < high) {
        int mid = (low + high) / 2;
        mergeSort(arr, tmp, low, mid);  
        mergeSort(arr, tmp, mid+1, high);
        merge(arr, tmp, low, mid, high);
      }
}
 
void merge(int[] arr, int[] tmp, int low, int mid, int high) {
 
    for(int i=low, i<=high ; i++) 
        tmp[i] = arr[i];
 
    int tmpLeft = low;
    int tmpRight = mid+1;
    int current = low;
 
    while(tmpLeft <= mid && tmpRight <= high) {
        if(tmp[tmpLeft] <= tmp[tmpRight]) 
               arr[current] = tmp[tmpLeft++];
        else
            arr[current] = tmp[tmpRight++];
        current++;
     }
 
    int remain = mid - tmpLeft;
    for(int i=0 ; i<=remain ; i++)
        arr[current+i] = tmp[tmpLeft+i];
}

4. Quicksort (분할교환정렬)

무작위로 선정된 한 원소를 사용하여 배열을 분할하고, 이 원소보다 작은 원소들은 앞에, 큰 원소는 뒤로 보낸다.

W(n)=O(n^2), A(n)=O(nlogn)

void quickSort(int[] arr, int low, int high) {
    int index = partition(arr, low, high);
    
    if(low < index-1)
        quickSort(arr, low, index-1);
    if(index < high)
        quickSort(arr, index, high);
}
 
int partition(int[] arr, int low, int high) {
    int pivot = arr[(low+high)/2];
 
    while(low <= high) {
        while(arr[low] < pivot)
            low++;
        while(pivot < arr[high])
            high--;
        if(low <= high) {
            swap(arr, low, high);
            low++;
            high--;
        }
    }
    return low;
}

출처: 코딩 인터뷰 완전 분석