이 튜토리얼에서는 주어진 배열을 여러 번 반복하여 연결한 뒤 만들어지는 새로운 배열에서 최대 하위 배열 합계(maximum subarray sum)를 구하는 프로그램을 C++로 작성하는 방법을 알아봅니다.
문제 조건은 다음과 같습니다. 길이가 n인 배열과 정수 K가 주어질 때, 원본 배열을 K번 이어 붙인 배열을 생각하고, 그 안에서 연속된 요소들의 합이 가장 커지는 하위 배열을 찾아 그 합계를 반환해야 합니다.
접근 방법: 카데인 알고리즘(Kadane's Algorithm)
이 문제는 유명한 카데인 알고리즘을 활용하면 간단하게 해결할 수 있습니다. 실제로 배열을 K번 복사해 메모리에 저장하는 대신, 인덱스를 모듈로 연산(i % n)으로 처리하면 반복된 배열을 탐색하는 것과 동일한 효과를 얻을 수 있습니다.
알고리즘의 핵심 동작은 다음과 같습니다.
1. 현재 위치까지의 누적 합(max_ending_here)을 계산하고, 음수가 되면 0으로 초기화합니다.
2. 탐색 과정에서 발견한 최댓값(max_so_far)을 계속 갱신합니다.
3. 전체 반복 횟수는 n × K이며, 인덱스는 i % n으로 원본 배열을 순환 참조합니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// 반복된 배열에서 최대 하위 배열 합계를 반환하는 함수
int maxSubArraySumRepeated(int a[], int n, int k) {
int max_so_far = INT_MIN, max_ending_here = 0;
// i % n으로 인덱스를 순환시켜 배열을 k번 반복한 효과를 냄
for (int i = 0; i < n*k; i++) {
max_ending_here = max_ending_here + a[i%n];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
// 부분합이 음수가 되면 0으로 초기화하여 재시작
if (max_ending_here < 0) max_ending_here = 0;
}
return max_so_far;
}
int main() {
int a[] = {10, 20, -30, -1};
int n = sizeof(a)/sizeof(a[0]);
int k = 3;
cout << "Maximum contiguous sum is "
<< maxSubArraySumRepeated(a, n, k);
return 0;
}실행 결과
Maximum contiguous sum is 30
결과 해석
예제에서 배열 {10, 20, -30, -1}을 3번 반복하면 [10, 20, -30, -1, 10, 20, -30, -1, 10, 20, -30, -1]이 됩니다. 이 배열에서 합이 가장 큰 연속 하위 배열은 [10, 20]이며, 그 합은 30입니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n × K) — 배열을 K번 반복하는 만큼 순회
- 공간 복잡도: O(1) — 추가 배열 없이 변수 두 개만 사용
참고로 K가 매우 클 경우에는 배열 전체 합이 양수일 때 접두사·접미사 합을 활용해 O(n)으로 최적화할 수도 있습니다.