문제 소개
정수 배열이 주어졌을 때, 배열을 원형(circular) 구조로 간주하여 만들 수 있는 부분 배열 중 합이 가장 큰 값을 찾는 것이 이 글의 목표입니다. 원형 배열에서는 마지막 요소 뒤에 다시 첫 번째 요소가 이어지기 때문에, 배열의 끝부분과 시작부분을 동시에 포함하는 부분 배열도 후보가 될 수 있습니다. 이것이 일반적인 최대 부분 배열 문제와의 가장 큰 차이점입니다.
입력 · 출력 예시
입력 − int arr[] = {1, 2, 8, 4, 3, 0, 7}
출력 − 최대 원형 부분 배열 합계: 22
설명 − 배열 {1, 2, 8, 4, 3, 0, 7}에서 합이 최대가 되는 부분 배열은 7 + 1 + 2 + 8 + 4 = 22입니다. 마지막 요소 7 다음에 첫 번째 요소 1이 이어지는 원형 구조 덕분에 이러한 조합이 가능합니다.
입력 − int arr[] = {2, 5, -1, 6, 9, 4, -5}
출력 − 최대 원형 부분 배열 합계: 25
설명 − 배열 {2, 5, -1, 6, 9, 4, -5}에서 합이 최대가 되는 부분 배열은 4 + 2 + 5 − 1 + 6 + 9 = 25입니다.
알고리즘 접근 방법
이 문제는 잘 알려진 카데인 알고리즘(Kadane's Algorithm)을 확장하면 O(n) 시간 안에 해결할 수 있습니다. 핵심 아이디어는 정답이 되는 부분 배열이 다음 두 가지 경우 중 하나라는 점입니다.
- 원형으로 감싸지 않는 경우 — 일반적인 배열처럼 연속된 구간의 합이 최대인 경우로, 카데인 알고리즘으로 최대 합을 구합니다.
- 원형으로 감싸지는 경우 — 배열의 끝과 시작을 걸치는 경우로, 이때 선택되지 않은 중간 구간의 합이 최소가 됩니다. 따라서 '전체 합 − 최소 부분 배열 합'으로 계산할 수 있습니다.
두 값 중 더 큰 값이 최종 답이 됩니다.
단계별 풀이
- 양수와 음수가 섞여 있는 정수 배열을 입력받습니다.
- 배열의 크기(size)를 계산합니다.
- 배열과 크기를 함수에 전달해 처리를 진행합니다.
- 전체 합을 저장할 변수
total을 0으로 초기화한 뒤, 반복문으로 모든 요소의 합을 구합니다. - 네 개의 변수를 arr[0]으로 초기화합니다. 각각
temp(현재 위치에서 끝나는 최대 구간 합),temp_2(전체 최대 구간 합),temp_3(현재 위치에서 끝나는 최소 구간 합),temp_4(전체 최소 구간 합)의 역할을 합니다. - i를 1부터 배열 크기까지 반복하면서 다음을 갱신합니다.
temp = max(temp + arr[i], arr[i]),temp_2 = max(temp_2, temp),temp_3 = min(temp_3 + arr[i], arr[i]),temp_4 = min(temp_4, temp_3) - 배열 크기가 1이면 arr[0]을 그대로 반환합니다.
- 최소 구간 합(temp_4)이 전체 합(total)과 같다면 모든 요소가 음수라는 의미이므로, 원형으로 감싸는 경우는 배제하고 temp_2를 반환합니다.
- 그렇지 않으면 max(temp_2, total − temp_4)를 계산해 반환합니다.
- 결과를 출력합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
int total = 0;
for (int i = 0; i < size; i++){
total += arr[i];
}
int temp = arr[0]; // 현재 위치에서 끝나는 최대 구간 합
int temp_2 = arr[0]; // 전체 최대 구간 합 (카데인 결과)
int temp_3 = arr[0]; // 현재 위치에서 끝나는 최소 구간 합
int temp_4 = arr[0]; // 전체 최소 구간 합
for (int i = 1; i < size; i++){
temp = max(temp + arr[i], arr[i]);
temp_2 = max(temp_2, temp);
temp_3 = min(temp_3 + arr[i], arr[i]);
temp_4 = min(temp_4, temp_3);
}
if (size == 1){
return arr[0];
}
// 모든 요소가 음수면 원형으로 감싸는 경우는 제외
if (temp_4 == total){
return temp_2;
}
int max_sum = max(temp_2, total - temp_4);
return max_sum;
}
int main(){
int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
Maximum circular subarray sum is: 25
복잡도 및 정리
이 알고리즘은 배열을 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가 배열 없이 상수 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 카데인 알고리즘으로 최대 구간 합과 최소 구간 합을 동시에 추적하고, '원형으로 감싸는 경우'를 전체 합에서 최소 구간 합을 빼는 방식으로 처리한다는 점만 기억하면 원형 배열 문제도 손쉽게 해결할 수 있습니다.