이 문제에서는 n개의 양의 정수로 이루어진 배열 arr[]와 하나의 정수 k가 주어집니다. 우리의 목표는 해당 크기의 모든 부분 배열(subarray)의 합이 k보다 작거나 같은 가장 큰 부분 배열의 크기를 구하는 것입니다.
문제 설명
배열의 원소들로 만들 수 있는 특정 크기의 모든 부분 배열에 대해, 그 합이 k 이하가 되도록 하는 부분 배열의 최대 길이를 찾아야 합니다.
예제로 이해하기
입력
arr[n] = {4, 1, 3, 2}, k = 9출력
3
설명
크기가 3인 모든 부분 배열과 그 합은 다음과 같습니다.
{4, 1, 3} = 8
{1, 3, 2} = 6크기가 3인 모든 부분 배열의 합이 k(=9) 이하이므로, 정답은 3입니다.
접근 방법 1: 접두사 합(Prefix Sum)과 이진 탐색 활용
가장 간단한 방법은 조건을 만족하지 않게 되는 경계를 찾는 것입니다. 이를 위해 각 인덱스까지의 원소 합을 저장하는 접두사 합(prefix sum) 배열을 만듭니다.
핵심 아이디어는 다음과 같습니다. 어떤 크기 m의 부분 배열 중 하나라도 합이 k를 초과한다면, 그보다 큰 크기의 부분 배열 역시 조건을 만족할 수 없습니다. 반대로 크기 m의 모든 부분 배열의 합이 k 이하라면 더 큰 크기도 가능한지 확인할 수 있습니다. 이러한 단조성(monotonicity) 덕분에 이진 탐색으로 최적의 크기를 효율적으로 찾을 수 있습니다.
구현 코드
#include<iostream>
using namespace std;
int calcSubArraySize(int arr[], int n, int k){
int prefixSum[n + 1];
prefixSum[0] = 0;
for (int i = 0; i < n; i++)
prefixSum[i + 1] = prefixSum[i] + arr[i];
// 크기 탐색 (이진 탐색)
int maxLen = -1;
int start = 1, end = n;
int mid, i;
while (start <= end){
int mid = (start + end) / 2;
for (i = mid; i <= n; i++){
if (prefixSum[i] - prefixSum[i - mid] > k)
break;
}
if (i == n + 1){
start = mid + 1;
maxLen = mid;
}
else
end = mid - 1;
}
return maxLen;
}
int main(){
int arr[] = {4, 1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 9;
cout<<"모든 부분 배열의 합이 k 이하가 되는 최대 크기: "<<calcSubArraySize(arr, n, k);
return 0;
}
이 방법은 시간 복잡도 O(n log n)으로 효율적이지만, 더 개선된 방법이 존재합니다.
접근 방법 2: 슬라이딩 윈도우(Sliding Window) 기법
두 번째 접근 방식은 슬라이딩 윈도우 기법을 사용하여 부분 배열의 합을 관리합니다. 처음에는 전체 배열을 윈도우로 삼고, 합이 k를 초과하는 순간 왼쪽 원소를 하나씩 제거하며 윈도우를 축소합니다. 이 과정에서 조건을 만족하는 최대 길이를 추적할 수 있습니다.
배열의 모든 원소가 양수이므로, 원소를 제거하면 합이 반드시 감소한다는 성질을 이용해 각 원소를 한 번씩만 방문하는 O(n) 알고리즘을 구현할 수 있습니다.
구현 코드
#include <iostream>
using namespace std;
int calcSubArraySizeSW(int arr[], int n, int k){
int maxLen = n;
int subArraySum = 0;
int start = 0;
for (int end = 0; end < n; end++){
subArraySum += arr[end];
while (subArraySum > k) {
subArraySum -= arr[start];
start++;
maxLen = min(maxLen, end - start + 1);
if (subArraySum == 0)
break;
}
if (subArraySum == 0) {
maxLen = -1;
break;
}
}
return maxLen;
}
int main(){
int arr[] = { 4, 1, 3, 2, 6 };
int k = 12;
int n = sizeof(arr)/ sizeof(arr[0]);
cout<<"모든 부분 배열의 합이 k 이하가 되는 최대 크기: "<<calcSubArraySizeSW(arr, n, k);
return 0;
}
출력 결과
모든 부분 배열의 합이 k 이하가 되는 최대 크기: 4
정리
이 문제는 두 가지 방법으로 해결할 수 있습니다. 접두사 합과 이진 탐색을 결합하면 O(n log n)의 시간 복잡도를 얻을 수 있고, 슬라이딩 윈도우 기법을 사용하면 O(n)으로 더욱 효율적으로 해결할 수 있습니다. 양의 정수 배열이라는 전제 조건 덕분에 슬라이딩 윈도우 방식이 유효하게 동작한다는 점을 기억하세요.