문제 소개
정수 배열이 주어졌을 때, 최소 k개 이상의 연속된 원소를 포함하는 부분 배열(subarray) 중에서 합이 가장 큰 값을 찾는 것이 이번 튜토리얼의 목표입니다. 단순한 슬라이딩 윈도우만으로는 'k개 미만'의 경우를 배제하기 어렵기 때문에, 카데인 알고리즘(Kadane's Algorithm)과 슬라이딩 윈도우 기법을 함께 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다.
알고리즘 단계
프로그램을 완성하기 위한 단계는 다음과 같습니다.
- 배열을 초기화합니다.
- 크기가 n인 max_sum 배열을 초기화합니다.
- 카데인 알고리즘을 이용해 각 인덱스까지 도달했을 때의 최대 부분 배열 합을 계산하여 max_sum 배열에 저장합니다.
- 처음 k개 원소의 합을 계산하여 변수 sum에 저장합니다.
- i = k부터 n까지 반복하는 루프를 작성합니다.
- sum에 a[i] - a[i - k]를 더해 윈도우를 한 칸 이동시킵니다.
- result를 max(result, sum)으로 갱신합니다. (정확히 k개 이상의 연속 구간)
- result를 max(result, sum + max_sum[i - k])으로 갱신합니다. (현재 윈도우 앞쪽에 추가로 붙일 수 있는 최대 합 구간을 확장)
여기서 max_sum[i - k]는 현재 윈도우 바로 앞까지의 최대 부분 배열 합을 의미하므로, 정확히 k개짜리 윈도우에 그 이상의 원소를 덧붙이는 모든 경우를 자연스럽게 커버하게 됩니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include<bits/stdc++.h>
using namespace std;
int getMaxSum(int a[], int n, int k) {
int maxSum[n];
maxSum[0] = a[0];
int currentMax = a[0];
for (int i = 1; i < n; i++) {
currentMax = max(a[i], currentMax+a[i]);
maxSum[i] = currentMax;
}
int sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i];
}
int result = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i-k];
result = max(result, sum);
result = max(result, sum + maxSum[i-k]);
}
return result;
}
int main() {
int a[] = {5, 3, 7, -5, 6, 2, 1};
int k = 6;
cout << getMaxSum(a, 7, k) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
19
예제 배열 {5, 3, 7, -5, 6, 2, 1}에서 k = 6일 때, 전체 배열의 합은 19이며 이것이 조건을 만족하는 최대 합입니다.
마무리
이 알고리즘은 카데인 알고리즘으로 각 위치별 최대 합을 미리 계산해 두고, 슬라이딩 윈도우로 정확히 k개 크기의 구간 합을 유지하면서 두 결과를 조합하는 방식입니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n)으로 매우 효율적입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.