C++로 구현하는 크기 k의 겹치지 않는 두 부분 배열의 최대 합 찾기

문제 이해하기

이 문제에서는 양의 정수로 이루어진 배열과 숫자 k가 주어집니다. 우리의 목표는 주어진 크기(k)를 가지면서 서로 겹치지 않는 두 부분 배열(subarray)의 합이 최대가 되도록 만드는 프로그램을 작성하는 것입니다.

즉, 크기가 k인 서로 겹치지 않는(서로 다른) 두 부분 배열을 찾아 그 합이 최대가 되도록 출력해야 합니다.

예시를 통해 문제를 자세히 살펴보겠습니다.

입력

array = {7, 1, 6, 9, 2} , k = 2

출력

{7, 1} , {6, 9}

설명

크기가 2인 모든 부분 배열:
{7, 1} : 합 = 7+1 = 8
{1, 6} : 합 = 1+6 = 7
{6, 9} : 합 = 6+9 = 15
{9, 2} : 합 = 9+2 = 11

최대 합을 가지면서 서로 겹치지 않는 두 부분 배열은 {7,1}과 {6,9}입니다.

해결 접근 방법

이 문제를 해결하는 가장 단순한 방법은 가능한 모든 부분 배열과 그 합을 구한 뒤, 서로 겹치지 않으면서 합이 최대인 두 부분 배열을 찾는 것입니다. 하지만 이 방식은 배열의 길이가 길어질수록 계산량이 급격히 늘어나 비효율적입니다.

더 효율적인 방법은 접두사 합(prefix sum) 배열을 활용하는 것입니다. 접두사 합 배열은 배열의 첫 번째 원소부터 각 위치까지의 누적 합을 미리 저장해 두는 배열로, 이를 사용하면 임의의 구간 합을 단순한 뺄셈 한 번으로 즉시 계산할 수 있습니다.

접두사 합 배열을 준비한 후에는 오른쪽에서 왼쪽으로 배열을 훑으며, 현재 위치보다 오른쪽에 있는 크기 k짜리 부분 배열 중 합이 가장 큰 것을 계속 추적합니다. 그리고 각 위치에서 왼쪽 부분 배열(현재 위치에서 시작하는 크기 k짜리 구간)과 앞서 추적한 오른쪽 최대 부분 배열을 더한 값이 지금까지의 최댓값보다 크면 결과를 갱신합니다. 이 알고리즘의 시간 복잡도는 O(N), 공간 복잡도는 O(N)으로 매우 효율적입니다.

C++ 구현 코드

다음은 위에서 설명한 해결 방법을 구현한 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
int findSubArraySum(int sum[], int i, int j){
    if (i == 0)
        return sum[j];
    else
        return (sum[j] - sum[i - 1]);
}
void maxSubarray(int arr[],int N, int K){
    int prefixsum[N];
    prefixsum[0] = arr[0];
    for (int i = 1; i < N; i++)
    prefixsum[i] = prefixsum[i - 1] + arr[i];
    pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
    int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) + findSubArraySum(prefixsum, N - K, N - 1);
    pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1));
    for (int i = N - 2 * K - 1; i >= 0; i--){
        int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1);
        if (cur >= secondSubarrayMax.second)
            secondSubarrayMax = make_pair(i + K, cur);
        cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second;
        if (cur >= maxSubarraySum){
            maxSubarraySum = cur;
            resIndex = make_pair(i, secondSubarrayMax.first);
        }
    }
    cout<<"{ ";
    for (int i = resIndex.first; i <resIndex.first + K; i++)
        cout<<arr[i]<<" ";
    cout<<"}"<<endl<<"{ ";
    for (int i = resIndex.second; i < resIndex.second + K; i++)
        cout<<arr[i]<<" ";
    cout<<"}"<<endl;
}
int main(){
    int arr[] = {2, 5, 1, 2, 7, 3, 0};
    int N = sizeof(arr) / sizeof(int);
    int K = 2;
    cout<<"Two non-overlapping subarrays with maximum sum are \n";
    maxSubarray(arr, N, K);
    return 0;
}

실행 결과

Two non-overlapping subarrays with maximum sum are
{ 2 5 }
{ 7 3 }

위 실행 결과에서 볼 수 있듯이, 입력 배열 {2, 5, 1, 2, 7, 3, 0}에서 크기가 2이면서 서로 겹치지 않는 두 부분 배열 중 합이 최대가 되는 조합은 {2, 5}(합 7)와 {7, 3}(합 10)이며, 전체 합은 17입니다.