이 글에서는 C++을 사용하여 합이 K보다 작은 부분 배열(subarray)의 개수를 구하는 방법을 다룹니다. 문제의 조건은 다음과 같습니다. 배열 arr[]와 정수 K가 주어질 때, 원소들의 합이 K보다 작은 모든 부분 배열을 찾아 그 개수를 구해야 합니다.
예제
입력 : arr[] = {1, 11, 2, 3, 15}
K = 10
출력 : 4
{1}, {2}, {3}, {2, 3}위 예제에서 합이 10보다 작은 부분 배열은 {1}, {2}, {3}, {2, 3}으로 총 4개입니다.
문제 해결 접근 방식
이 문제는 크게 두 가지 방법으로 해결할 수 있습니다. 하나는 직관적인 브루트 포스(Brute Force) 방식이고, 다른 하나는 시간 복잡도를 크게 줄여주는 슬라이딩 윈도우(Sliding Window) 기법입니다.
방법 1: 브루트 포스 (완전 탐색)
가장 기본적인 접근 방식은 가능한 모든 부분 배열을 하나씩 순회하면서 각각의 합을 계산하고, 그 합이 K보다 작을 때마다 정답 카운트를 1씩 증가시키는 것입니다.
코드 예제
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // 주어진 배열
int k = 10; // 주어진 k
int size = sizeof(arr) / sizeof(int); // 배열의 크기
int ans = 0; // 정답을 세는 카운터 변수
for(int i = 0; i < size; i++){ // 외부 루프: 시작 인덱스
int sum = 0;
for(int j = i; j < size; j++){ // 내부 루프: 끝 인덱스
sum = sum + arr[j];
if(sum < k) // 합이 k보다 작은지 비교
ans++; // 조건을 만족하면 정답 증가
}
}
cout << ans << "\n";
return 0;
}실행 결과
4
이 방법은 구현이 간단하지만, 모든 부분 배열을 탐색해야 하므로 시간 복잡도가 O(N²)(N은 배열의 크기)로 매우 높습니다. 배열의 크기가 커지면 실행 시간이 급격히 늘어나기 때문에 비효율적입니다.
방법 2: 슬라이딩 윈도우 기법 (효율적인 접근)
브루트 포스와 달리, 슬라이딩 윈도우 기법은 모든 부분 배열을 일일이 확인하지 않습니다. 대신 오른쪽 경계(end)를 한 칸씩 이동하며 누적합을 관리하고, 부분 배열의 합이 K 이상이 되면 왼쪽 경계(start)를 오른쪽으로 밀어 합을 줄입니다. 이 과정을 배열 전체를 순회할 때까지 반복합니다.
코드 예제
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // 주어진 배열
int k = 10; // 주어진 k
int size = sizeof(arr) / sizeof(int); // 배열의 크기
int ans = 0; // 정답을 세는 카운터 변수
int start = 0; // 왼쪽 경계
int end = 0; // 오른쪽 경계
int sum = 0;
while(end < size && start < size){ // 배열 전체를 순회할 때까지
while(sum >= k && start < end){
sum = sum - arr[start];
start++; // 합이 k 이상이면 왼쪽 경계를 이동
}
if(end >= start)
ans = ans + end - start;
sum += arr[end];
end++; // 오른쪽 경계를 한 칸 이동
}
cout << ans << "\n";
return 0;
}실행 결과
4
이처럼 슬라이딩 윈도우 기법을 활용하면 프로그램의 실행 속도가 크게 향상되어, 입력 크기가 매우 큰 경우에도 빠르게 동작합니다.
코드 동작 원리 상세 설명
이 접근 방식의 핵심은 다음과 같습니다. 평소에는 부분 배열의 합이 K보다 작은 동안 오른쪽 경계를 계속 확장하며, 조건을 만족하는 경우의 수를 정답에 더해갑니다. 코드에서 결정적인 변화는 합이 K 이상이 되는 순간 발생합니다. 이때 합이 K 미만이 될 때까지 왼쪽 경계를 오른쪽으로 이동시켜 윈도우의 크기를 줄입니다.
이 과정을 반복하면서 만들어지는 새로운 부분 배열들 중 합이 K보다 작은 것들이 정답에 차례대로 더해집니다. 각 위치에서 end - start만큼의 부분 배열이 한 번에 계산되므로, 전체 탐색 없이도 정답을 구할 수 있습니다.
이 방식은 앞서 살펴본 브루트 포스에 비해 훨씬 효율적이며, 시간 복잡도는 O(N)(N은 배열의 크기)입니다. 각 원소가 최대 두 번(왼쪽 경계와 오른쪽 경계에 의해) 방문되기 때문입니다.
마무리
이 글에서는 슬라이딩 윈도우 기법을 사용하여 합이 K보다 작은 부분 배열의 개수를 구하는 문제를 해결했습니다. 단순한 완전 탐색 방식과 효율적인 슬라이딩 윈도우 방식 두 가지 접근 방법을 C++ 코드와 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 문제 해결에 도움이 되기를 바랍니다.