개요
이 튜토리얼에서는 C++를 사용하여 합이 k보다 큰 가장 긴 부분 배열(subarray)의 길이를 찾는 프로그램을 작성해 보겠습니다. 배열에 음수가 포함될 수 있기 때문에 단순한 투 포인터 기법으로는 해결할 수 없으며, 누적 합(prefix sum)과 이진 탐색(binary search)을 함께 활용하는 것이 핵심 아이디어입니다.
문제 해결 접근 방법
전체적인 풀이 과정은 다음과 같습니다.
- 배열을 초기화합니다.
- 배열을 순회하면서 각 인덱스까지의 누적 합과 해당 인덱스를 pair 형태로 벡터에 저장합니다.
- 저장된 누적 합들을 합 값과 인덱스를 기준으로 오름차순 정렬합니다.
- 정렬된 결과에서 각 위치까지의 최소 인덱스를 저장할 배열을 준비합니다.
- n번 반복하는 루프에서 minIndexes[i]를 '이전 위치의 최소 인덱스'와 '현재 누적 합의 원래 인덱스' 중 더 작은 값으로 갱신합니다.
- 합(sum)을 0으로 초기화한 뒤 배열을 다시 한 번 순회합니다.
두 번째 순회에서는 아래 규칙에 따라 정답을 갱신합니다.
- 현재 요소를 합에 더합니다.
- 합이 k보다 큰 경우: 배열의 처음부터 현재 위치까지 전체가 조건을 만족하므로 최대 부분 배열 길이는 i + 1입니다.
- 그렇지 않은 경우: 정렬된 누적 합 배열에서 이진 탐색으로 sum - k - 1 이하인 값의 위치를 찾습니다. 해당 위치에 저장된 최소 인덱스가 현재 위치 i보다 작다면, 그 구간의 합이 k보다 크다는 의미이므로 i - minIndexes[ind]로 최대 길이를 갱신할 수 있습니다.
구현 예제
위에서 설명한 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
bool compare(const pair<int, int>& a, const pair<int, int>& b) {
if (a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
int findIndex(vector<pair<int, int> >& previousSums, int n, int val) {
int start = 0;
int end = n - 1;
int mid, result = -1;
while (start <= end) {
mid = (start + end) / 2;
if (previousSums[mid].first <= val) {
result = mid;
start = mid + 1;
}else {
end = mid - 1;
}
}
return result;
}
int getLargestSubArray(int arr[], int n, int k) {
int maxLength = 0;
vector<pair<int, int> > previousSums;
int sum = 0, minIndexes[n];
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
previousSums.push_back({ sum, i });
}
sort(previousSums.begin(), previousSums.end(), compare);
minIndexes[0] = previousSums[0].second;
for (int i = 1; i < n; i++) {
minIndexes[i] = min(minIndexes[i - 1], previousSums[i].second);
}
sum = 0;
for (int i = 0; i < n; i++) {
sum = sum + arr[i];
if (sum > k) {
maxLength = i + 1;
}else {
int ind = findIndex(previousSums, n, sum - k - 1);
if (ind != -1 && minIndexes[ind] < i) {
maxLength = max(maxLength, i - minIndexes[ind]);
}
}
}
return maxLength;
}
int main() {
int arr[] = { 5, 3, -3, 2, 4, 7 };
int k = 5, n = 6;
cout << getLargestSubArray(arr, n, k) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
6
예제 배열 { 5, 3, -3, 2, 4, 7 }에서 k = 5인 경우, 배열 전체(길이 6)의 합은 18로 5보다 크기 때문에 정답은 6이 됩니다.
시간 복잡도
누적 합 계산에는 O(n)이 소요되고, 정렬에 O(n log n), 각 위치마다 이진 탐색을 수행하므로 역시 O(n log n)이 필요합니다. 따라서 전체 시간 복잡도는 O(n log n)입니다.
마무리
이번 튜토리얼에서는 누적 합과 이진 탐색을 결합하여 합이 k보다 큰 가장 긴 부분 배열을 효율적으로 찾는 방법을 살펴보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨 주세요.