분할 정복 알고리즘 (Divide and Conquer)

분할 정복 알고리즘 (Divide and Conquer)

분할 정복 알고리즘(Divide and Conquer)은 문제를 더 작고 독립적인 하위 문제로 분할하고, 각 하위 문제를 해결한 후 결과를 합쳐서 원래의 문제를 해결하는 알고리즘 디자인 기법입니다. 이 방법은 문제를 재귀적으로 해결하는 과정에서 큰 문제를 점진적으로 해결할 수 있도록 도와줍니다. 이 글에서는 분할 정복 알고리즘의 정의, 특징, 그리고 구현 예제(Java와 C)를 통해 그 개념을 이해하고 실제 활용 방법을 살펴보겠습니다.

1. 분할 정복 알고리즘의 정의

분할 정복 알고리즘은 다음과 같은 단계를 통해 문제를 해결합니다:

1. 분할 (Divide): 해결해야 할 문제를 여러 개의 더 작은 하위 문제로 나눕니다.
2. 정복 (Conquer): 각 하위 문제를 재귀적으로 해결합니다. 하위 문제가 충분히 작아지면 직접 해결할 수 있습니다.
3. 병합 (Combine): 하위 문제의 해결 결과를 합쳐서 전체 문제의 해를 구합니다.

대표적인 분할 정복 알고리즘으로는 병합 정렬 (Merge Sort), 퀵 정렬 (Quick Sort), 이진 검색 (Binary Search) 등이 있습니다.

2. 분할 정복 알고리즘의 특징

• 재귀적 접근: 분할 정복은 재귀를 통해 문제를 반복적으로 쪼개고 해결합니다.
• 문제의 분할: 문제를 나눔으로써 연산의 복잡도를 줄이고, 더 효율적으로 문제를 해결할 수 있습니다.
• 시간 복잡도 개선: 많은 경우 분할 정복을 사용하면 시간 복잡도를 크게 개선할 수 있습니다. 예를 들어, 병합 정렬은 시간 복잡도가 (O(n \log n))으로 효율적입니다.

3. 예제: 병합 정렬 (Merge Sort)

병합 정렬은 분할 정복을 대표적으로 사용하는 정렬 알고리즘 중 하나입니다. 병합 정렬의 동작 방식은 다음과 같습니다:

1. 배열을 중간으로 나눕니다.
2. 각 하위 배열을 병합 정렬을 사용해 정렬합니다.
3. 정렬된 두 배열을 하나로 병합합니다.

아래는 병합 정렬을 Java와 C로 구현한 예제입니다.

Java 구현

public class MergeSort {
    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;

            // 분할 단계
            mergeSort(array, left, middle);
            mergeSort(array, middle + 1, right);

            // 병합 단계
            merge(array, left, middle, right);
        }
    }

    private static void merge(int[] array, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; ++i)
            leftArray[i] = array[left + i];
        for (int j = 0; j < n2; ++j)
            rightArray[j] = array[middle + 1 + j];

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        mergeSort(array, 0, array.length - 1);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}

C 구현

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int left, int middle, int right) {
    int n1 = middle - left + 1;
    int n2 = right - middle;

    int* leftArray = (int*)malloc(n1 * sizeof(int));
    int* rightArray = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        leftArray[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArray[j] = arr[middle + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            i++;
        } else {
            arr[k] = rightArray[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArray[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArray[j];
        j++;
        k++;
    }

    free(leftArray);
    free(rightArray);
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;

        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arrSize = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, arrSize - 1);

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

4. 분할 정복 알고리즘의 장단점

장점

• 병렬 처리 가능성: 분할된 하위 문제들은 서로 독립적이기 때문에 병렬적으로 처리할 수 있는 가능성이 높습니다.
• 복잡도 감소: 문제를 분할하고 해결하므로 많은 경우 시간 복잡도가 크게 줄어듭니다. 예를 들어, 병합 정렬과 퀵 정렬 모두 (O(n \log n))의 시간 복잡도를 가집니다.

단점

• 재귀 호출 오버헤드: 분할 정복은 재귀 호출을 많이 사용하므로, 재귀 호출에 따른 오버헤드가 발생할 수 있습니다. 특히, 재귀 깊이가 깊어지면 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.
• 추가 메모리 사용: 병합 정렬의 경우, 추가적인 배열을 사용하기 때문에 메모리 사용량이 증가할 수 있습니다.

5. 결론

분할 정복 알고리즘은 문제를 작은 단위로 나누어 해결하는 강력한 방법입니다. 병합 정렬, 퀵 정렬, 이진 검색 등 다양한 알고리즘이 분할 정복의 개념을 바탕으로 설계되었습니다. 이러한 알고리즘들은 복잡한 문제를 해결할 때 매우 유용하며, 특히 큰 데이터 집합을 다룰 때 유리합니다.

이번 포스팅에서는 병합 정렬을 예제로 Java와 C 언어로 구현해 보았습니다. 이를 통해 분할 정복의 원리와 구현 방법을 더 깊이 이해할 수 있기를 바랍니다.