정수 배열에서 최대 부분 배열 합 찾기: 세 가지 접근 방식

정수 배열이 주어졌을 때, 그 안에서 연속된 부분 배열 중 합이 가장 큰 부분 배열을 찾아 그 합을 반환하는 것은 고전적인 알고리즘 문제입니다. 이 문제는 다양한 최적화 기법을 통해 해결할 수 있으며, 여기서는 세 가지 주요 접근 방식인 무차별 대입(Brute Force), 분할 정복(Divide and Conquer), 그리고 동적 계획법(Dynamic Programming)을 다룹니다. 특히, 대규모 데이터셋에서는 시간 복잡도 O(N)을 요구하므로 동적 계획법이 필수적입니다.

1. 무차별 대입 방식 (Brute Force)

가장 직관적인 방법은 주어진 배열에서 가능한 모든 연속 부분 배열을 생성하고, 각 부분 배열의 합을 계산하여 이들 중 최대값을 찾는 것입니다. 이 방식은 세 개의 중첩된 반복문을 사용하여 모든 시작점, 모든 끝점, 그리고 그 사이의 모든 요소를 탐색합니다. 결과적으로 시간 복잡도는 O(N³)이 됩니다.

#include <vector>
#include <algorithm> // std::max 사용
#include <limits>    // std::numeric_limits<int>::min() 사용

// 최대 부분 배열의 무차별 대입 풀이
int findMaxSubarrayBruteForce(const std::vector<int>& dataArray) {
    int globalMaxSum = std::numeric_limits<int>::min(); // 전체 배열에서 찾은 최대 합계

    // 모든 가능한 시작 인덱스 (startIdx)
    for (size_t startIdx = 0; startIdx < dataArray.size(); ++startIdx) {
        // 모든 가능한 끝 인덱스 (endIdx), 시작 인덱스보다 크거나 같아야 함
        for (size_t endIdx = startIdx; endIdx < dataArray.size(); ++endIdx) {
            int currentSubarraySum = 0; // 현재 부분 배열의 합계

            // startIdx부터 endIdx까지의 합계 계산
            for (size_t k = startIdx; k <= endIdx; ++k) {
                currentSubarraySum += dataArray[k];
            }
            // 현재 부분 배열의 합계가 전역 최대 합계보다 크면 업데이트
            globalMaxSum = std::max(globalMaxSum, currentSubarraySum);
        }
    }
    return globalMaxSum;
}

2. 분할 정복 방식 (Divide and Conquer)

분할 정복 접근법은 배열을 절반으로 나누고, 최대 부분 배열 합이 다음 세 가지 경우 중 하나에 속할 수 있다는 아이디어에 기반합니다:

최대 합이 왼쪽 절반 배열 안에만 존재하는 경우.
최대 합이 오른쪽 절반 배열 안에만 존재하는 경우.
최대 합이 중앙을 가로지르는 경우 (즉, 왼쪽 절반의 일부와 오른쪽 절반의 일부를 포함하는 경우).

첫 두 경우는 재귀적으로 해결할 수 있습니다. 세 번째, 중앙을 가로지르는 경우는 특별한 처리가 필요합니다. 이 경우, 중앙 원소를 포함하면서 왼쪽으로 확장하는 최대 합과, 중앙 원소 다음부터 오른쪽으로 확장하는 최대 합을 각각 계산한 후 이 둘을 합산합니다.

예를 들어, 배열 {-5, 2, -3, 6, -1, 3, 1, -2, 7}이 주어졌을 때, 중앙 인덱스에 있는 -1을 기준으로 생각해봅시다. 중앙을 가로지르는 최대 부분 배열을 찾기 위해:

-1부터 왼쪽으로 확장하면서 최대 합을 찾습니다. 이 때, [6, -1]의 합은 5가 되고, [2, -3, 6, -1]의 합은 4가 됩니다. 최대 합은 6을 포함하는 5입니다.
-1 바로 다음 원소인 3부터 오른쪽으로 확장하면서 최대 합을 찾습니다. 이 때, [3, 1, -2, 7]의 합은 9가 됩니다.

따라서, 중앙을 가로지르는 최대 부분 배열 합은 5 (왼쪽 최대) + 9 (오른쪽 최대) = 14가 됩니다. 최종적으로 왼쪽 절반의 최대 합, 오른쪽 절반의 최대 합, 그리고 중앙을 가로지르는 최대 합 중 가장 큰 값을 반환합니다.

#include <vector>
#include <algorithm> // std::max 사용
#include <limits>    // std::numeric_limits<int>::min() 사용

// 중앙을 가로지르는 최대 부분 배열 합계를 찾는 도우미 함수
int findMaxCrossingSum(const std::vector<int>& arr, int low, int mid, int high) {
    int leftSum = std::numeric_limits<int>::min();
    int currentSum = 0;
    // 중앙부터 왼쪽으로 최대 합계 찾기 (mid 포함)
    for (int i = mid; i >= low; --i) {
        currentSum += arr[i];
        if (currentSum > leftSum) {
            leftSum = currentSum;
        }
    }

    int rightSum = std::numeric_limits<int>::min();
    currentSum = 0;
    // 중앙 다음부터 오른쪽으로 최대 합계 찾기 (mid+1 포함)
    for (int i = mid + 1; i <= high; ++i) {
        currentSum += arr[i];
        if (currentSum > rightSum) {
            rightSum = currentSum;
        }
    }

    // 왼쪽 또는 오른쪽 합계가 유효하지 않은 경우 (모든 음수, 또는 빈 범위 등) 처리
    // 두 합계가 모두 유효하면 더하고, 그렇지 않으면 유효한 쪽만 반환
    if (leftSum == std::numeric_limits<int>::min()) return rightSum;
    if (rightSum == std::numeric_limits<int>::min()) return leftSum;
    
    return leftSum + rightSum;
}

// 최대 부분 배열의 분할 정복 풀이 재귀 함수
int findMaxSubarrayDivConq(const std::vector<int>& arr, int low, int high) {
    if (low == high) {
        return arr[low]; // 배열에 원소가 하나뿐인 경우
    }

    int mid = low + (high - low) / 2; // 중간 인덱스 계산 (오버플로우 방지)

    // 1. 왼쪽 절반에서 최대 부분 배열 합 찾기
    int maxLeftSum = findMaxSubarrayDivConq(arr, low, mid);
    // 2. 오른쪽 절반에서 최대 부분 배열 합 찾기
    int maxRightSum = findMaxSubarrayDivConq(arr, mid + 1, high);
    // 3. 중앙을 가로지르는 최대 부분 배열 합 찾기
    int maxCrossingSum = findMaxCrossingSum(arr, low, mid, high);

    // 세 가지 경우 중 가장 큰 값을 반환 (C++11 initializer list 사용)
    return std::max({maxLeftSum, maxRightSum, maxCrossingSum});
}

// 분할 정복 방식의 메인 함수
int maxSubarraySumDivideAndConquer(const std::vector<int>& nums) {
    if (nums.empty()) {
        return 0; // 빈 배열 처리
    }
    return findMaxSubarrayDivConq(nums, 0, static_cast<int>(nums.size() - 1));
}

3. 동적 계획법 (Dynamic Programming) - Kadane's Algorithm

이 방법은 최대 부분 배열 문제를 O(N)의 시간 복잡도로 해결할 수 있는 가장 효율적인 접근 방식입니다. 카데인 알고리즘(Kadane's Algorithm)으로 알려져 있으며, 핵심 아이디어는 현재 위치까지의 최대 부분 배열 합을 효율적으로 계산하는 것입니다.

알고리즘은 배열을 한 번 순회하면서 두 가지 값을 추적합니다:

현재_최대_합 (currentSubarraySum): 현재까지 탐색한 원소를 포함하는 부분 배열 중 가장 큰 합.
전체_최대_합 (overallMaxSum): 배열 전체에서 발견된 최대 부분 배열 합.

각 원소를 순회할 때마다 currentSubarraySum은 (이전_currentSubarraySum + 현재_원소)와 현재_원소 자체 중 더 큰 값으로 업데이트됩니다. 이는 현재 원소를 새로운 부분 배열의 시작으로 간주할지, 아니면 이전 부분 배열에 추가할지 결정하는 것을 의미합니다. 만약 currentSubarraySum이 음수가 된다면, 해당 부분 배열은 더 이상 이어질 필요가 없다는 의미이므로 currentSubarraySum을 현재 원소 자체로 재설정하는 것입니다. 그리고 overallMaxSum은 항상 overallMaxSum과 currentSubarraySum 중 더 큰 값으로 업데이트됩니다.

이 과정을 통해 배열의 모든 원소를 단 한 번만 검토하며 최대 부분 배열 합을 찾을 수 있습니다. 모든 숫자가 음수일 경우에도 올바르게 작동하며, 이 때는 배열 내 가장 큰(가장 덜 음수인) 숫자가 결과가 됩니다.

#include <vector>
#include <algorithm> // std::max 사용

// 최대 부분 배열의 동적 계획법 풀이 (카데인 알고리즘)
int findMaxSubarrayKadane(const std::vector<int>& numbers) {
    if (numbers.empty()) {
        return 0; // 빈 배열에 대한 처리 (혹은 적절한 예외)
    }

    int overallMaxSum = numbers[0];     // 배열 전체에서 발견된 최대 합 (최소한 첫 번째 원소)
    int currentSubarraySum = numbers[0]; // 현재까지의 부분 배열 합

    // 두 번째 원소부터 배열 끝까지 순회
    for (size_t idx = 1; idx < numbers.size(); ++idx) {
        // 현재 원소부터 새로운 부분 배열을 시작하는 것과
        // 현재 원소를 이전 부분 배열에 추가하는 것 중 더 큰 값을 선택
        currentSubarraySum = std::max(numbers[idx], currentSubarraySum + numbers[idx]);
        
        // 전체 최대 합 업데이트
        overallMaxSum = std::max(overallMaxSum, currentSubarraySum);
    }

    return overallMaxSum;
}

태그: C++ 알고리즘 동적계획법 분할정복 배열

7월 13일 17:10에 게시됨

괴물 클럽

정수 배열에서 최대 부분 배열 합 찾기: 세 가지 접근 방식

1. 무차별 대입 방식 (Brute Force)

2. 분할 정복 방식 (Divide and Conquer)

3. 동적 계획법 (Dynamic Programming) - Kadane's Algorithm

인기 태그