이 튜토리얼에서는 특정 크기의 모든 하위 배열(subarray)의 합이 k보다 작거나 같도록 만드는 최대 하위 배열 크기를 찾는 프로그램을 C++로 구현하는 방법을 다룹니다.
문제 정의
크기가 N인 배열과 하나의 정수 k가 주어집니다. 우리의 목표는 다음 조건을 만족하는 하위 배열의 최대 길이를 구하는 것입니다.
조건: 주어진 배열에서 해당 길이를 가지는 모든 하위 배열의 합이 k 이하여야 합니다.
예를 들어, 배열이 {1, 2, 10, 4}이고 k = 14라고 가정해 보겠습니다. 길이가 2인 모든 하위 배열의 합은 최대 12(2 + 10)이므로 조건을 만족하지만, 길이가 3인 경우 2 + 10 + 4 = 16으로 k를 초과하므로 답은 2가 됩니다.
접근 방법: 누적 합과 이진 탐색
이 문제는 누적 합(Prefix Sum)과 이진 탐색(Binary Search)을 결합하면 효율적으로 해결할 수 있습니다.
1단계: 누적 합 배열 생성
먼저 원본 배열의 누적 합 배열을 만듭니다. 누적 합을 사용하면 임의의 구간 합을 O(1) 시간에 계산할 수 있습니다. 즉, 인덱스 i부터 시작하는 길이 mid인 하위 배열의 합은 prefixsum[i] - prefixsum[i - mid]로 바로 구할 수 있습니다.
2단계: 이진 탐색으로 최대 길이 확인
길이 후보(mid)에 대해 해당 길이의 모든 하위 배열의 합이 k 이하인지 검사합니다. 조건을 만족하면 더 긴 길이를 시도하고(탐색 범위를 오른쪽으로 이동), 만족하지 않으면 더 짧은 길이를 시도합니다(탐색 범위를 왼쪽으로 이동). 이 과정을 반복하면 최종적으로 조건을 만족하는 최대 길이를 얻을 수 있습니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
// 최대 길이의 하위 배열을 찾는 함수
int bsearch(int prefixsum[], int n, int k) {
int ans = -1;
// 이진 탐색 수행
int left = 1, right = n;
while (left <= right) {
int mid = (left + right) / 2;
int i;
for (i = mid; i <= n; i++) {
if (prefixsum[i] - prefixsum[i - mid] > k)
break;
}
if (i == n + 1) {
left = mid + 1;
ans = mid;
}
else right = mid - 1;
}
return ans;
}
// 최대 하위 배열 크기를 반환하는 함수
int maxSize(int arr[], int n, int k) {
int prefixsum[n + 1];
memset(prefixsum, 0, sizeof(prefixsum));
for (int i = 0; i < n; i++)
prefixsum[i + 1] = prefixsum[i] + arr[i];
return bsearch(prefixsum, n, k);
}
int main() {
int arr[] = {1, 2, 10, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 14;
cout << maxSize(arr, n, k) << endl;
return 0;
}실행 결과
2
동작 원리 상세 분석
예제 입력 arr = {1, 2, 10, 4}, k = 14의 경우 프로그램은 다음과 같이 동작합니다.
먼저 누적 합 배열은 {0, 1, 3, 13, 17}이 됩니다. 이진 탐색은 길이 2를 검사할 때, 가능한 모든 하위 배열 {1,2}, {2,10}, {10,4}의 합이 각각 3, 12, 14로 모두 k 이하임을 확인합니다. 그러나 길이 3을 검사하면 {2,10,4}의 합이 16으로 k를 초과하므로 실패합니다. 따라서 최종 결과로 2가 출력됩니다.
시간 복잡도
누적 합 배열 생성에는 O(N), 각 길이 후보에 대한 검사에는 O(N)이 소요되며, 이진 탐색으로 O(log N)번 검사를 수행하므로 전체 시간 복잡도는 O(N log N)입니다. 단순히 모든 길이를 하나씩 시도하는 브루트 포스 방식(O(N²))보다 효율적입니다.