4. 알고리즘 분할과 정복

알고리즘의 분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 분할하고, 각 부분 문제를 독립적으로 해결한 후 그 결과를 결합하여 원래의 문제를 해결하는 방법입니다. 이러한 분할 정복은 재귀적인 방식으로 구현되며, 문제를 보다 작은 부분 문제로 분할하고, 각 부분 문제의 결과를 결합하는 과정을 거칩니다.

분할 정복 알고리즘의 세 가지 단계

1. 분할(Divide)

주어진 문제를 작은 부분 문제로 분할합니다. 이 단계에서는 주로 문제의 크기를 절반으로 줄이는 방식으로 분할을 수행합니다.

2. 정복(Conquer)

분할된 부분 문제들을 재귀적으로 해결합니다. 각 부분 문제는 독립적으로 해결되며, 이 단계에서는 가장 작은 단위의 문제에 대한 해결 방법을 제시합니다.

3. 결합(Combine)

부분 문제의 해결 방법을 결합하여 원래의 문제에 대한 해결 방법을 구축합니다. 이 단계에서는 각 부분 문제의 결과를 조합하거나 결합하여 최종 해결책을 도출합니다.

분할 정복 알고리즘의 예시

1. 병합 정렬(Merge Sort)

배열을 절반으로 분할하고, 각 부분 배열을 재귀적으로 정렬한 후, 정렬된 부분 배열을 병합하여 전체 배열을 정렬하는 알고리즘입니다.

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

        mergeSort(arr, left, mid); // 왼쪽 부분 배열 정렬
        mergeSort(arr, mid + 1, right); // 오른쪽 부분 배열 정렬

        merge(arr, left, mid, right); // 정렬된 부분 배열 병합
    }
}

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

    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }

    for (int j = 0; j < n2; j++) {
        rightArr[j] = arr[mid + 1 + j];
    }

    int i = 0;
    int j = 0;
    int k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

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

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

위의 병합 정렬 예시에서 mergeSort 함수는 배열을 왼쪽과 오른쪽으로 분할하고, 분할된 부분 배열을 재귀적으로 정렬합니다. 그리고 merge 함수에서는 정렬된 부분 배열을 병합하여 전체 배열을 정렬합니다.

병합 정렬은 분할 과정에서 배열을 절반으로 나누기 때문에, 배열의 길이를 n이라고 할 때 시간 복잡도는 O(n log n)입니다. 이는 배열을 일정한 비율로 분할하여 정렬하기 때문에 효율적인 정렬 알고리즘이라고 할 수 있습니다.

2. 퀵 정렬(Quick Sort)

배열에서 하나의 원소를 기준으로 작은 값과 큰 값으로 분할한 후, 각 부분 배열을 재귀적으로 정렬하는 알고리즘입니다.

동작 과정은 배열에서 하나의 원소를 피벗으로 선택합니다. 일반적으로 첫 번째 원소, 마지막 원소, 중간 원소 등을 피벗으로 선택하고피벗을 기준으로 배열을 분할합니다. 피벗보다 작은 값은 피벗의 왼쪽에 위치하고, 피벗보다 큰 값은 피벗의 오른쪽에 위치하도록 배열을 재배치합니다. 이 과정을 퀵 정렬의 핵심 단계로 생각할 수 있습니다.분할된 작은 부분 배열에 대해 재귀적으로 퀵 정렬을 수행합니다. 이 단계에서는 피벗을 다시 선택하여 부분 배열을 분할하고 정렬합니다.정렬된 부분 배열을 결합하여 전체 배열을 완성합니다.

퀵 정렬의 구현은 다양한 방식으로 이루어질 수 있지만, 가장 일반적인 방식은 Lomuto 파티션 스키마나 Hoare 파티션 스키마를 사용하는 것입니다. 아래는 Lomuto 파티션 스키마를 사용한 퀵 정렬의 예시 코드입니다.

public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high); // 피벗을 기준으로 배열을 분할
        quickSort(arr, low, pivotIndex - 1); // 피벗의 왼쪽 부분 배열을 정렬
        quickSort(arr, pivotIndex + 1, high); // 피벗의 오른쪽 부분 배열을 정렬
    }
}

public int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; // 피벗으로 배열의 마지막 원소를 선택
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j); // 작은 값과 i번째 원소를 교환
        }
    }

    swap(arr, i + 1, high); // 피벗과 i + 1번째 원소를 교환
    return i + 1; // 피벗의 최종 위치를 반환
}

public void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

위의 예시 코드에서 quickSort 함수는 배열을 퀵 정렬하는 역할을 합니다. partition 함수는 피벗을 기준으로 배열을 분할하고 피벗의 최종 위치를 반환합니다. 이렇게 재귀적으로 분할과 정렬을 수행하여 배열이 정렬됩니다.

퀵 정렬의 평균 시간 복잡도는 O(n log n)이며, 최악의 경우에도 O(n^2)입니다. 그러나 대부분의 경우에 퀵 정렬은 매우 빠르게 동작하며, 빠른 정렬 알고리즘 중에서 가장 많이 사용됩니다.

3. 이진 검색(Binary Search)

분할 정복 알고리즘에서 이진 검색(Binary Search)은 대표적인 예시입니다. 이진 검색은 정렬된 배열에서 특정한 값을 찾는 알고리즘으로, 중간 값과 비교하여 찾고자 하는 값이 중간 값보다 작으면 왼쪽 부분 배열을, 중간 값보다 크면 오른쪽 부분 배열을 탐색하는 방식입니다. (자세히보기)

분할 정복 알고리즘은 문제를 더 작은 부분 문제로 분할하여 해결하므로, 일반적으로 재귀적인 구현을 사용합니다. 이러한 알고리즘은 문제를 효율적으로 해결할 수 있는 경우가 많으며, 대부분의 경우 시간 복잡도가 효율적입니다. 하지만 분할과 결합 과정에서 추가적인 연산이 필요할 수 있으므로, 문제의 성격에 따라 효율성을 고려하여 구현해야 합니다.