[C++로 배우는 알고리즘과 자료구조] Day 29: 분할 정복 기법

분할 정복 기법 (Divide and Conquer)

분할 정복 기법은 문제를 더 작은 부분 문제로 나누어 해결한 후, 그 결과를 결합하여 전체 문제의 해를 구하는 알고리즘 설계 기법입니다. 대표적인 예로 합병 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있습니다.

분할 정복 기법의 주요 단계:

1. 분할 (Divide): 문제를 더 작은 부분 문제로 나눕니다.
2. 정복 (Conquer): 각 부분 문제를 재귀적으로 해결합니다.
3. 결합 (Combine): 부분 문제의 해를 결합하여 전체 문제의 해를 구합니다.

대표적인 분할 정복 알고리즘: 합병 정렬

합병 정렬 (Merge Sort)

합병 정렬은 분할 정복 기법을 사용하는 효율적인 정렬 알고리즘입니다. 배열을 반으로 나누어 각각을 정렬한 후, 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병합니다.

합병 정렬의 시간 복잡도:

• 평균 및 최악의 경우: (O(n \log n))

합병 정렬의 구현

#include <iostream>
#include <vector>

// 병합 함수
void merge(std::vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    std::vector<int> L(n1);
    std::vector<int> R(n2);

    for (int i = 0; i < n1; ++i) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        R[j] = arr[mid + 1 + j];
    }

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

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

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

// 합병 정렬 함수
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

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

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

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};

    std::cout << "정렬 전 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    mergeSort(arr, 0, arr.size() - 1);

    std::cout << "정렬 후 배열: ";
    for (int value : arr) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    return 0;
}

 

분할 정복 기법의 장단점

장점:

• 병렬화 가능: 각 부분 문제를 독립적으로 해결할 수 있어 병렬화가 용이합니다.
• 효율성: 대부분의 경우 시간 복잡도가 (O(n \log n))으로 효율적입니다.

단점:

• 오버헤드: 재귀 호출과 함수 호출로 인한 오버헤드가 발생할 수 있습니다.
• 추가 메모리 사용: 부분 문제를 저장하기 위한 추가 메모리가 필요할 수 있습니다.

분할 정복의 예: 최대 부분 배열 문제

최대 부분 배열 문제는 주어진 배열에서 연속된 부분 배열의 합이 최대가 되는 부분 배열을 찾는 문제입니다.

카다네 알고리즘 (Kadane's Algorithm)

카다네 알고리즘은 이 문제를 해결하는 효율적인 방법 중 하나로, 동적 계획법을 사용합니다. 그러나 분할 정복 기법을 사용하여도 문제를 해결할 수 있습니다.

최대 부분 배열 문제의 분할 정복 구현

#include <iostream>
#include <vector>
#include <climits>

// 교차하는 부분 배열의 최대 합 계산 함수
int maxCrossingSum(const std::vector<int>& arr, int left, int mid, int right) {
    int sum = 0;
    int leftSum = INT_MIN;

    for (int i = mid; i >= left; --i) {
        sum += arr[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }

    sum = 0;
    int rightSum = INT_MIN;
    for (int j = mid + 1; j <= right; ++j) {
        sum += arr[j];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }

    return leftSum + rightSum;
}

// 최대 부분 배열의 합 계산 함수
int maxSubArraySum(const std::vector<int>& arr, int left, int right) {
    if (left == right) {
        return arr[left];
    }

    int mid = left + (right - left) / 2;

    int leftSum = maxSubArraySum(arr, left, mid);
    int rightSum = maxSubArraySum(arr, mid + 1, right);
    int crossingSum = maxCrossingSum(arr, left, mid, right);

    return std::max({leftSum, rightSum, crossingSum});
}

int main() {
    std::vector<int> arr = {2, 3, 4, 5, 7};
    int maxSum = maxSubArraySum(arr, 0, arr.size() - 1);

    std::cout << "최대 부분 배열의 합: " << maxSum << std::endl;

    return 0;
}

설명

1. 병합 함수 (Merge Function):
   • 두 개의 정렬된 하위 배열을 하나의 정렬된 배열로 합병합니다.
   • 좌측 및 우측 하위 배열을 저장한 후, 비교하여 원래 배열에 다시 합병합니다.
2. 최대 부분 배열 문제:
   • 주어진 배열에서 연속된 부분 배열의 합이 최대가 되는 부분 배열을 찾는 문제입니다.
   • 교차하는 부분 배열의 최대 합을 계산한 후, 좌측, 우측, 교차하는 부분 배열의 최대 합 중 최대값을 반환합니다.

분할 정복 기법의 기본 개념과 대표적인 알고리즘인 합병 정렬과 최대 부분 배열 문제를 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 알고리즘과 다양한 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 30: 알고리즘 문제 해결 및 코딩 테스트 준비"에 대해 학습하겠습니다.