이 글에서는 C++ 프로그램을 사용하여 주어진 범위 내에 합이 존재하는 부분 배열(subarray)의 개수를 구하는 방법을 다룹니다. 양의 정수로 이루어진 배열 arr[]과 범위 {L, R}가 주어졌을 때, 합이 L부터 R 사이에 속하는 부분 배열의 총 개수를 계산해야 합니다.
먼저 문제를 이해하기 위한 간단한 예시를 살펴보겠습니다.
입력 : arr[] = {1, 4, 6}, L = 3, R = 8
출력 : 3
해당 부분 배열은 {1, 4}, {4}, {6}입니다.
입력 : arr[] = {2, 3, 5, 8}, L = 4, R = 13
출력 : 6
해당 부분 배열은 {2, 3}, {2, 3, 5}, {3, 5},
{5}, {5, 8}, {8}입니다.문제 해결 접근 방법
이 문제는 C++로 두 가지 방법으로 해결할 수 있습니다.
1. 브루트 포스(Brute Force) 접근법
가장 기본적인 방법은 모든 부분 배열의 합을 일일이 계산한 뒤, 그 합이 주어진 범위 내에 존재하는지 확인하는 것입니다. 하지만 이 방법은 시간 복잡도가 O(n²)이므로(n은 배열의 크기) 많은 시간이 소요된다는 단점이 있습니다.
2. 효율적인 접근법 — 슬라이딩 윈도우(Sliding Window)
시간을 절약하기 위해 슬라이딩 윈도우 기법을 활용한 효율적인 방법을 사용할 수 있습니다. 이 기법을 활용하면 O(n)의 시간 복잡도로 훨씬 빠르게 결과를 계산할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int subCount(int *arr, int n, int x){
int start = 0, end = 0, sum = 0, count = 0;
while (end < n){ // 이 루프에서 오른쪽 경계를 이동합니다
sum = sum + arr[end];
while(start <= end && sum >= x){ // 이 루프는 왼쪽 경계를 이동합니다
sum = sum - arr[start]; // 왼쪽 경계를 이동하면서 합을 감소시킵니다.
// 이전 요소들을 제외하기 위함입니다.
start++; // 왼쪽 경계를 이동합니다.
}
count = count + ((end - start) + 1); // 부분 배열의 개수를 셉니다.
end++;
}
return count;
}
int main(){
int n; // 배열의 크기
int L, R;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++)
cin >> arr[i];
cin >> L >> R;
int answer;
answer = subCount(arr, n, R) - subCount(arr, n, (L - 1)); // 최종 답안.
cout << answer << "\n";
return 0;
}
출력
1
코드 설명
이 접근법에서는 먼저 주어진 범위의 상한보다 합이 작은 부분 배열의 개수를 구하고, 여기서 범위의 하한 미만인 부분 배열의 개수를 subCount 함수를 통해 빼주는 방식으로 최종 답을 계산합니다.
subCount 함수 동작 원리
subCount 함수는 슬라이딩 윈도우 기법을 사용하여 합이 x보다 작은 부분 배열의 개수를 찾습니다.
처음에는 'start'와 'end'를 모두 0으로 초기화합니다. 배열을 순회하면서 start부터 end까지 요소들의 합을 유지합니다. 만약 start와 end가 같아지고 합이 x보다 크거나 같다면, start를 이동시키면서 요소를 합에서 제거하여 합을 줄여나갑니다.
이 과정은 합이 x보다 작아지거나 start가 end보다 커질 때까지 반복됩니다. 그다음 부분 배열의 개수만큼 count를 증가시키고, 오른쪽 경계(end)를 1 증가시킵니다. 외부 루프가 종료되면 부분 배열의 총 개수를 반환합니다.
결론
이 글에서는 슬라이딩 윈도우 기법을 활용하여 주어진 범위 내 합을 가지는 부분 배열의 개수를 O(n)의 시간 복잡도로 구하는 문제를 해결했습니다. 또한 C++ 프로그램 예제와 함께 브루트 포스 방식과 효율적인 방식 두 가지 접근법을 학습했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다.