Divide and Conquer

Tae_Tae·2024년 9월 3일

자료구조 / 알고리즘 (C)

목록 보기

14/26

분할 정복 알고리즘 개요

분할 정복(Divide and Conquer) 알고리즘은 문제를 더 작은 하위 문제들로 분할하고, 각 하위 문제를 해결한 후, 그 결과를 결합하여 전체 문제를 해결하는 알고리즘 전략입니다.
이 방법은 재귀적으로 문제를 해결하며, 많은 복잡한 문제들을 효율적으로 해결할 수 있는 강력한 도구입니다.

퀵 정렬(Quicksort) 알고리즘

퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘의 일종으로, 평균적으로 $O(n \log n)$ 의 시간 복잡도를 가지는 매우 효율적인 정렬 알고리즘입니다.

퀵 정렬은 피벗(Pivot)이라는 기준점을 선택한 후, 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 배치하는 과정을 재귀적으로 반복하여 정렬을 수행합니다.

퀵 정렬의 단계

피벗 선택 : 배열에서 하나의 요소를 피벗으로 선택합니다. 일반적으로 배열의 마지막 요소를 피벗으로 선택합니다.
분할 : 피벗을 기준으로 배열을 분할합니다. 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 배치되도록 배열을 재정렬합니다.
재귀적 정렬 : 분할된 두 개의 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 이 과정을 배열의 크기가 1이 될 때까지 반복합니다.

퀵 정렬 예시 코드

#include <stdio.h>

void quicksort(int ary[], int left, int right) {
    if (left < right) {
        int pivotIndex = partition(ary, left, right);
        quicksort(ary, left, pivotIndex - 1);
        quicksort(ary, pivotIndex + 1, right);
    }
}

int partition(int ary[], int left, int right) {
    int pivot = ary[right];
    int i = left - 1;

    for (int j = left; j < right; j++) {
        if (ary[j] <= pivot) {
            i++;
            int temp = ary[i];
            ary[i] = ary[j];
            ary[j] = temp;
        }
    }

    int temp = ary[i + 1];
    ary[i + 1] = ary[right];
    ary[right] = temp;
    return i + 1;
}

int main(void) {
    int ary[] = { 3, 7, 8, 5, 2, 1, 9, 5, 4 };
    int n = sizeof(ary) / sizeof(ary[0]);

    quicksort(ary, 0, n - 1);

    for (int i = 0; i < n; i++) {
        printf("%d ", ary[i]);
    }
    return 0;
}

장점

효율성 : 평균적으로 $O(n \log n)$ 의 시간 복잡도를 가지며, 실제로도 빠르게 동작합니다.

제자리 정렬 : 추가적인 메모리 사용 없이 정렬을 수행합니다.

단점

최악의 경우 : 피벗이 항상 최소 또는 최대 값으로 선택될 경우, 시간 복잡도가 $O(n^2)$ 로 악화될 수 있습니다. 하지만, 랜덤 피벗 선택 또는 삼중 피벗 방식을 사용하면 최악의 경우를 회피할 수 있습니다.

정리

퀵 정렬은 많은 경우에 있어 효율적인 선택이며, C 언어의 qsort 함수는 퀵 정렬을 내부적으로 사용하여 매우 빠른 정렬을 제공합니다.

퀵 셀렉트(Quickselect) 알고리즘

퀵 셀렉트 알고리즘은 선택 알고리즘 중 하나로, 주어진 배열에서 $k$ 번째로 큰(또는 작은) 요소를 찾는 데 사용됩니다.

퀵 셀렉트는 퀵 정렬(Quicksort)에서 사용하는 분할 방식(Partitioning)을 응용하여 목표로 하는 $k$ 번째 요소를 빠르게 찾습니다.

작동 방식

퀵 정렬과 유사하게 배열을 분할하지만, 정렬과 달리 전체 배열을 정렬하지 않고, $k$ 번째 요소만 찾는 데 집중합니다.

1. 피벗 선택 및 분할 :

배열의 마지막 요소를 피벗으로 선택합니다.
Partitioning(분할)을 통해 배열을 피벗을 기준으로 두 부분으로 나눕니다.
- 피벗보다 큰 값들은 배열의 왼쪽 부분에,
- 피벗보다 작은 값들은 배열의 오른쪽 부분에 위치하게 됩니다.
피벗은 자신의 정확한 위치에 놓이게 됩니다. 이 위치는 배열에서 피벗이 몇 번째로 큰 요소인지 나타냅니다.

2. k번째 요소와의 비교 :

분할이 완료된 후, 피벗의 위치가 $k$ 와 같은지 비교합니다.
피벗의 위치가 정확히 $k$ 라면, 피벗이 바로 k번째로 큰 요소입니다.
피벗의 위치가 $k$ 보다 크다면, 왼쪽 부분 배열에서 $k$ 번째 요소를 찾습니다.
피벗의 위치가 $k$ 보다 작다면, 오른쪽 부분 배열에서 $k$ - $k'$ 번째 요소를 찾습니다 ( $k'$ 는 피벗의 위치).

예시 코드

C 언어로 구현된 퀵 셀렉트 알고리즘입니다.

#include <stdio.h>

int partition(int ary[], int left, int right) {
    int pivot = ary[right];  // 마지막 요소를 피벗으로 선택
    int i = left;

    for (int j = left; j < right; j++) {
        if (ary[j] > pivot) {  // 피벗보다 큰 값을 왼쪽으로 이동
            int temp = ary[i];
            ary[i] = ary[j];
            ary[j] = temp;
            i++;
        }
    }

    ary[right] = ary[i];
    ary[i] = pivot;

    return i;
}

int quickselect(int ary[], int left, int right, int k) {
    if (left == right) {
        return ary[left];
    }

    int pivotIndex = partition(ary, left, right);

    if (pivotIndex == k) {
        return ary[pivotIndex];
    } else if (k < pivotIndex) {
        return quickselect(ary, left, pivotIndex - 1, k);
    } else {
        return quickselect(ary, pivotIndex + 1, right, k);
    }
}

int main(void) {
    int ary[] = {10, 40, 30, 20, 50};
    int n = sizeof(ary) / sizeof(ary[0]);
    int k = 2;  // 세 번째로 큰 요소를 찾기 위해 k = 2로 설정

    int kthLargest = quickselect(ary, 0, n - 1, k);

    printf("%d번째로 큰 요소: %d\n", k + 1, kthLargest);

    return 0;
}

시간 복잡도

퀵 셀렉트의 평균 시간 복잡도는 $O(n)$ 입니다. 이는 퀵 정렬의 평균 시간 복잡도인 $O(n \log n)$ 보다 효율적이며, $k$ 번째 요소만을 찾는 데 최적화되어 있습니다.
최악의 경우, 분할이 계속해서 한쪽으로 치우치는 경우, 시간 복잡도는 $O(n^2)$ 이 될 수 있습니다.
이를 방지하기 위해 피벗을 임의로 선택하는 등의 최적화 기법을 사용할 수 있습니다.

퀵 셀렉트와 퀵 정렬의 비교

퀵 정렬(Quick Sort)과 퀵 셀렉트(Quick Select)는 둘 다 분할 정복(Divide and Conquer) 알고리즘에 속하며, 피벗(pivot)을 기준으로 배열을 분할하는 과정이 유사합니다. 그러나 두 알고리즘의 목적과 작동 방식에는 중요한 차이점이 있습니다.

핵심 차이점

목적 :

퀵 정렬 : 전체 배열을 정렬하는 것이 목적입니다.
퀵 셀렉트 : 배열에서 k번째로 작은(혹은 큰) 요소를 찾는 것이 목적입니다.

정렬 범위 :

퀵 정렬 : 배열 전체를 재귀적으로 정렬합니다.
퀵 셀렉트 : 필요한 부분만 정렬하며, 전체 배열을 정렬하지 않습니다.

시간 복잡도 :

퀵 정렬 : 평균 시간 복잡도는 $O(n \log n)$ 입니다.
퀵 셀렉트 : 평균 시간 복잡도는 $O(n)$ 으로, 특정 위치의 요소만 찾기 때문에 더 효율적입니다.

정리 :

퀵 정렬과 퀵 셀렉트는 모두 피벗을 활용한 분할 정복 알고리즘을 사용하지만, 하나는 배열 전체의 정렬을 목표로 하고, 다른 하나는 특정 위치의 요소를 찾는 데 최적화되어 있습니다.

Tae_Tae

이전 포스트

Insertion Sort

다음 포스트