[알고리즘 공부] 분할 정복

0. 개요

분할 정복은 아마도 알고리즘 중 가장 기초적인 계념일 것이다.

대표적인 탐색 알고리즘 중 하나인 이진 탐색도 분할 정복 알고리즘 중 하나이기 때문이다.

이번에는 다양한 분할 정복 알고리즘에 대해 알아보고 정리해보려고 한다.

 

1. 알고리즘 개념

분할 정복(Divide and Conquer)은 말 그대로 문제를 분할하고

분할된 작은 문제들을 해결한 뒤 결과를 합치는 것이다.

 

대표적인 알고리즘으로는 병합 정렬, 퀵 정렬, 이진 탐색이 있다.

 

1) 병합 정렬

병합 정렬은 대표적인 분할 정복 접근의 정렬 알고리즘이다.

 

1) 배열을 반으로 계속 나누고

2) 나뉜 배열을 각각 정렬한 뒤

3) 정렬된 배열을 병합하면서 전체를 정렬하는 알고리즘이다.

 

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;
    int i = left;
    int j = mid + 1;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }

    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);

    for (int k = left; k <= right; k++)
        arr[k] = temp[k - left];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);
}

int main() {
    vector<int> arr = {5, 2, 3, 1};
    mergeSort(arr, 0, arr.size() - 1);

    for (int x : arr) cout << x << " ";
}

 

2) 퀵 정렬

퀵 정렬은 하나의 피벗을 기준으로 큰 값과 작은 값을 나누고,

나뉜 부분을 다시 재귀적으로 정렬하는 알고리즘이다.

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[right]);    
    return i + 1;  
}

void quickSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int pi = partition(arr, left, right);
    
    quickSort(arr, left, pi - 1);
    quickSort(arr, pi + 1, right);
}

int main() {
    vector<int> arr = {5, 3, 8, 4, 2, 7, 1, 6};
    quickSort(arr, 0, arr.size() - 1);

    for (int x: arr) cout << x << " ";
}

 

3) 이진 탐색

이진 탐색은 정렬되어 있는 배열에서 원하는 값을 빠르게 찾는 알고리즘이다.

 

1. 배열의 가운데를 확인한 후

2. 찾으려고 하는 값과 비교한 후, 값이 더 큰가 작은가에 따라

3. 오른쪽 혹은 왼쪽 절반만 다시 탐색한다.

 

결과적으로 O(logN) 속도를 낼 수 있다.

#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1; // 없음
}