C++로 반복 연결한 배열에서 최대 부분 배열 합 구하기

이 문제에서는 크기가 n인 배열 arr[]와 정수 k가 주어집니다. 우리의 과제는 arr를 k번 반복 연결하여 만든 배열에서 최대 부분 배열(subarray) 합을 찾는 프로그램을 작성하는 것입니다.

문제 설명

배열 arr를 k번 반복하여 새로운 배열을 생성한 뒤, 그 배열에서 얻을 수 있는 부분 배열 합의 최댓값을 구하는 것이 목표입니다.

예시

예제를 통해 문제를 이해해 보겠습니다.

입력

arr[] = {-9, -5, 14, 6} k = 2

출력

26

설명

반복 후 새 배열 : {-9, -5, 14, 6, -9, -5, 14, 6}
최대 합을 가지는 부분 배열 = {14, 6, -9, -5, 14, 6}
합 = 26

해결 접근 방법 1: 배열 생성 후 카데인 알고리즘 적용

가장 단순한 방법은 arr[]를 k번 연결하여 새 배열을 만든 다음, 그 배열에서 최대 합을 가지는 부분 배열을 찾는 것입니다. 이때 가장 적합한 알고리즘은 카데인(Kadane) 알고리즘입니다.

카데인 알고리즘은 배열을 한 번 순회하면서 누적 합이 음수가 되면 0으로 초기화하고, 그 과정에서 나타난 최댓값을 추적하는 방식으로 선형 시간에 최대 부분 배열 합을 구할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
    int newArr[2*n];
    for(int i = 0; i < k*n; i++)
    newArr[i] = arr[i%n];
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k*n; i++) {
        sum = sum + newArr[i];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}
int main(){
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"반복 연결 후 생성된 배열의 최대 부분 배열 합은 "<<calcMaxSubArraySum(arr, n, k);
    return 0;
}

출력

반복 연결 후 생성된 배열의 최대 부분 배열 합은 26

해결 접근 방법 2: 모듈러 연산 활용 (더 효율적)

위 방법도 좋지만, 모듈러 연산(modular arithmetic)을 활용하면 실제로 배열을 생성하지 않고도 더 효율적으로 문제를 해결할 수 있습니다.

모듈러 연산이란 나머지 연산자(%)를 사용하여 식의 나머지를 구하는 것을 말합니다. 인덱스 i에 대해 arr[i % n]처럼 접근하면, 반복 연결된 배열에서 해당 위치의 원소를 직접 참조하는 것과 같은 효과를 얻습니다.

즉, 반복 연결로 새 배열을 만드는 대신 arr[i % n]으로 원소를 읽으면 됩니다. 나머지 로직은 첫 번째 방법과 동일합니다.

예제 코드

#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
    int maxSum = -1000, sum = 0;
    for (int i = 0; i < k*n; i++) {
        sum = sum + arr[i%n];
        if (maxSum < sum)
            maxSum = sum;
        if (sum < 0)
            sum = 0;
    }
    return maxSum;
}
int main(){
    int arr[] = { -9, -5, 14, 6 };
    int k = 2;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"반복 연결 후 생성된 배열의 최대 부분 배열 합은 "<<calcMaxSubArraySum(arr, n, k);
    return 0;
}

출력

반복 연결 후 생성된 배열의 최대 부분 배열 합은 26

복잡도 분석

두 방법 모두 시간 복잡도는 O(k×n)으로 동일하지만, 모듈러 연산 방식은 반복 배열을 저장하기 위한 추가 메모리가 전혀 필요 없으므로 공간 복잡도 면에서 훨씬 유리합니다. 따라서 k나 n이 커지는 경우에는 모듈러 연산 기반 접근 방식을 사용하는 것이 바람직합니다.