이 글에서 우리는 C++를 사용하여 합이 K보다 작은 부분배열의 수를 알아낼 것이다. 이 문제에서 배열 arr[]와 정수 K가 있습니다. 이제 합이 K보다 작은 하위 배열을 찾아야 합니다. 예는 다음과 같습니다. -
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3} 해결 방법 찾기
이제 우리는 주어진 문제를 해결하기 위해 두 가지 다른 방법을 사용할 것입니다 -
브루트 포스
이 접근 방식에서는 모든 하위 배열을 반복하고 합계를 계산하고 합계가 k보다 작은 경우 k와 비교하여 답을 증가시킵니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
for(int i = 0; i < size; i++){ // outer loop.
int sum = 0;
for(int j = i; j < size; j++){ // inner loop.
sum = sum + arr[j];
if(sum < k) // comparing with k.
ans++; // incrementing our ans if sum is less than k.
}
}
cout << ans << "\n";
return 0;
} 출력
4
그러나 이 접근 방식은 시간 복잡도가 매우 높기 때문에 그다지 좋지 않습니다. O(N*N) , 여기서 n은 배열의 크기입니다.
Sliding Window 방법을 사용하는 다른 솔루션을 살펴보겠습니다(프로그램의 시간 복잡성을 줄이는 데 도움이 됩니다).
효율적인 접근
무차별 대입과 달리 , 우리는 모든 하위 배열을 거치지 않을 것입니다. 대신, 하위 배열의 합이 k를 초과하고 왼쪽 경계를 오른쪽 경계까지 이동하고 전체 배열이 탐색될 때까지 계속 반복할 때만 탐색합니다.
예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 11, 2, 3, 15}; // given array
int k = 10; // given k
int size = sizeof(arr) / sizeof(int); // size of our array.
int ans = 0; // counter variable.
int start = 0; // left border.
int end = 0; // right border.
int sum = 0;
while(end < size && start < size){ // till the whole array is traversed.
while(sum >= k && start < end){
sum = sum - arr[start];
start++;
}
if(end >= start)
ans = ans + end - start;
sum += arr[end];
end++;
}
cout << ans << "\n";
return 0;
} 출력
4
슬라이딩 창 기법을 사용합니다. 이 접근 방식에서 더 큰 제약 조건에 대해 실행하기 위해 프로그램을 더 빠르고 효율적으로 만들 수 있습니다.
위 코드 설명
이 접근 방식에서 우리는 일반적으로 합이 k보다 작을 때까지 탐색하고 그에 따라 답을 증가시키는 것은 합이 k보다 크거나 같을 때 발생하는 코드의 중요한 변경입니다. 이 상황에서 우리는 왼쪽 경계를 오른쪽 경계보다 작게 또는 합이 k보다 크거나 같을 때까지 증가시키기 시작합니다. 더 처리하면 형성될 수 있는 다른 하위 배열을 통과합니다. 합이 k보다 작은 이러한 새 하위 배열이 우리의 답에 추가되므로 답이 증분됩니다.
이 접근 방식은 이전 Brute Force에 비해 매우 효율적입니다. 시간 복잡도가 O(N)이므로 적용했습니다. , 여기서 N은 배열의 크기입니다.
결론
이 기사에서는 슬라이딩 창 기법을 사용하여 합이 k보다 작은 부분배열의 수를 찾는 문제를 해결합니다. . 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식( Normal 및 Efficient)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.