[Algorithm] 분할정복

분할 정복

• 분할 : 해결할 문제를 여러 개의 작은 부분으로 나눈다
• 정복 : 나눈 작은 문제를 각각 해결한다
• 통합 : 해결된 해답을 모은다

거듭 제곱

x^n 을 구한다고 했을 때, 단순하게 x를 곱하면 n번의 연산이 필요하다. 과한 시간복잡도를 분할정복을 통해 낮출 수 있다.

int dcPower(int x, int n){
  if (n==0) retrun 1;
  if (n==1) retrun x;

  if (n % 2 == 0) { //even
    int ret = dcPower(x,n / 2);
    return ret * ret;
  } else { //odd
    int ret = dcPower(x, (n - 1) / 2);
    retrun ret * ret * x;
  }
}

병합 정렬

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식

void mergeSort(int arr[], int size){
  if (size == 1) return;

  int mid = size / 2;
  mergeSort(arr, mid);
  mergeSort(arr + mid, size - mid);

  int* buf = new int[size];
  int i = 0, j = mid, k = 0;
  while(i < mid %% j < size)
      buf[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
  while (i < mid)
      buf[k++] = arr[i++];
  while (j < size)
      buf[k++] = arr[j++];

  for(i = 0; i < size; i++)
    arr[i] = buf[i];

  delete buf;
}

퀵 정렬

주어진 배열을 두 개로 분할하고 각각을 정렬한다

• 병합정렬과 달리 두 부분을 pivot을 기준으로 대소로 나눠 분리한다
• 퀵 정렬은 각 부분 정렬이 끝난 후 병합의 후처리가 필요없다

void quickSort(int arr[], int left, int right){
  if (left < right) {
    int p = left, i = left + 1, j = right;
    while (i <= j){
        while (arr[i] <= arr[p]) i++;
        while (arr[j] > arr[p]) j--;

        if (i < j){
          int tmp = arr[i];
          arr[i] = arr[j];
          arr[j] = tmp;
        }
    }
    int tmp = arr[p];
    arr[p] = arr[j];
    arr[j] = tmp;

    quickSort(arr, left, j - 1);
    quickSort(arr, j + 1, right);
  }
}

이진 탐색

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

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

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

//반복
int binarySearch(int arr[], int size, int key){
  int low = 0, high = size - 1;

  while (low <= high) {
    int mid = (low + high) / 2;

    if (arr[mid] == key)
      return mid;
    else if (arr[mid] > key)
      high = mid - 1;
    else
      low = mid + 1;
  }

  return -1;
}

//재귀
int binarySearch(int arr[], int low, int high, int key){
  if (low > high) return -1;

  int mid = (low + high) / 2;

  if (arr[mid] == key)
      return mid;
    else if (arr[mid] > key)
      return binarySearch(arr, low, mid - 1, key);
    else
      return binarySearch(arr, mid + 1, high, key);
}