C++로 작성하여 합이 K보다 작은 하위 배열의 수를 찾습니다.

이 게시물에서는 C++를 사용하여 합이 K보다 작은 하위 배열의 수를 구해보겠습니다. 이 문제에는 배열 arr[]과 정수 K가 있습니다. 이제 합이 K보다 작은 하위 배열을 찾아야 합니다. 아래는 예입니다 −

Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}

해결책을 찾는 방법

이제 주어진 문제를 해결하기 위해 두 가지 다른 방법을 사용할 것입니다 -

무차별 대입

이 방법에서는 모든 하위 배열을 반복하고 그 합계와 합이 k보다 작으면 k와 비교하여 답을 늘립니다.

Example

#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

그러나 이 방법은 시간 복잡도가 매우 높기 때문에(n은 배열의 크기인 O(N*N)) 그다지 좋지 않습니다.

슬라이딩 윈도우 접근 방식을 사용하여 대체 솔루션을 찾아보겠습니다(이는 프로그램의 시간 복잡성을 줄이는 데 도움이 됩니다).

Efficient method

brute force

efficient method

Strong>과 달리 모든 하위 배열을 반복하지 않습니다. 대신 하위 배열의 합이 k 를 초과하는 경우에만 반복하여 왼쪽 경계를 오른쪽 경계로 이동하고 전체 배열을 탐색할 때까지 반복합니다.

Example

#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;
}

Output

4

우리는 Sliding Window Technique을 사용하여 더 큰 제약 조건을 처리할 때 프로그램을 더 빠르고 효율적으로 만듭니다.

위 코드에 대한 설명

이 접근 방식에서는 일반적으로 합계가 k보다 작을 때까지 반복하고 이를 기반으로 답을 증가시킵니다. 이는 합계가 k보다 크거나 같을 때 발생하는 코드의 주요 변경 사항입니다. . 이 경우 k보다 작거나 같거나 합이 k보다 크거나 같을 때까지 왼쪽 경계를 증가시키기 시작합니다. 처리가 더 진행됨에 따라 형성될 수 있는 다른 가능한 하위 배열을 반복합니다. k보다 작은 새 하위 배열의 합이 답에 추가되므로 답이 증가합니다.

이전의 무차별 대입 솔루션과 비교할 때 이 방법은 시간 복잡도가 O(N)이므로 매우 효율적입니다. 여기서 N은 배열의 크기입니다.

결론

이 논문에서는 슬라이딩 윈도우 기법을 사용하여 합이 k보다 작은 하위 배열의 개수를 찾는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(사소하고 효율적인)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++로 작성하여 합이 K보다 작은 하위 배열의 수를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!