분할정복

주어진 문제에 대해서 분할하여 각각의 문제를 해결하는 방법으로 하향식 접근 방식

1. 주어진 문제에 대해서 2개 이상의 작은 문제로 분할
2. 분할된 각각의 작은 문제들을 정복해 문제 해결
3. 필요시에 해결된 문제들을 다시 합쳐 원래 문제에 대한 해답을 구함

장점: 문제를 나눔으로서 어려운 문제를 해결할 수 있는 경우를 생성할 수 있다는 장점이 있고, 이를 위한 효율적인 알고리즘이 다량 존재,

단점: 함수를 재귀적으로 호출해야 하기 때문에 오버헤드 및 메모리 다량 보관에 대한 스택 오버플로우가 발생할 수 있음

예시) 이진탐색, 합병정렬, 퀵정렬,,,

---

이진탐색

정렬되어 있는 데이터에 대해서 탐색 방법

• 배열의 가운데 원소와 탐색하려는 값을 비교
• 성능: O(logN)

  탐색값 = 가운데 원소 -> 탐색 성공

  탐색값 < 가운데 원소 -> 이진 탐색 왼쪽 부분배열 호출

  탐색값 > 가운데 원소 -> 이진 탐색 오른쪽 부분배열 호출

소스

작성 언어: java

public int BinartSearch(int[] A, int left, int right, int B){
    if(left > right) return -1;
    
    int mid = (int) ((right - left) / 2);
    
    if( A[mid] == B ) return mid;
    else if( A[mid] < B ){
        BinartSearch(int[] A, mid+1, right, B);
    }
    else{
        BinartSearch(int[] A, left, mid-1, B);
    }
} 

---

합병정렬

배열의 정렬을 위해 분할정복 알고리즘을 사용하여 가장 작은 배열로 분할해서 정렬하고 합병하면서 정렬 처리

• 성능: O(NlogN)

작성 언어: java

//분할
private void mergeSort(int[] arr, int low, int high) {
       if (low >= high) { //종료 조건
           return;
       }

    int mid = low + ((high - low) / 2);
    mergeSort(arr, low, mid);//왼쪽
    mergeSort(arr, mid + 1, high);//오른쪽

    merge(arr, low, mid, high);
}

//합병
private void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int idx = 0;

    int left = low;
    int right = mid + 1;
    while (left <= mid && right <= high) {
        if (arr[left] <= arr[right]) {
            temp[idx] = arr[left];
            left++;
        } else {
            temp[idx] = arr[right];
            right++;
        }
        idx++
    }

    while (left <= mid) { //왼쪽 리스트에 값이 남아 있는 경우
            temp[idx] = arr[left];
            idx++;
            left++;
        }

    while (right <= high) { //오른쪽 리스트에 값이 남아 있는 경우
        temp[idx] = arr[right];
        idx++;
        right++;
    }

    for (int i = low; i <= high; i++) {
        arr[i] = temp[i - low];
    }
}

참고

https://minhamina.tistory.com/127

https://cdragon.tistory.com/entry/Algorithm-Merge-Sort%ED%95%A9%EB%B3%91-%EC%A0%95%EB%A0%AC