C++를 사용하여 보다 크거나 작지 않은 쿼리 작성

이 기사에서는 질문과 배열이 제공되며 답변해야 할 두 가지 유형의 쿼리가 있습니다.

• 0을 입력하세요 - x(주어진 값)보다 크거나 같은 요소의 수를 계산해야 합니다.
• 유형 1 - x(주어진 값)보다 엄격하게 큰 요소 수를 계산해야 합니다.

여기에 간단한 예가 있습니다 -

Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3
   Query 1: 0 50
   Query 2: 1 40
   Query 3: 0 30
Output :
   0
   1
   3
Explanation:
x = 50, q = 0 : No elements greater than or equal to 50.
x = 40, q = 1 : 45 is greater than 40.
x = 30, q = 0 : three elements 30, 40, 45 are greater than or equal to 30.

해결책을 찾는 방법

해결책을 찾는 데 사용할 수 있는 두 가지 방법이 있습니다. 먼저 무차별 대입 솔루션을 사용한 다음 더 높은 제약 조건에 대해 작동하는지 확인합니다. 해당되지 않는 경우 당사는 계속해서 솔루션을 최적화합니다.

무차별 솔루션

이 방법에서는 주어진 조건을 만족하는 모든 q 쿼리에 대해 배열을 반복하고 조건을 만족하는 숫자를 찾습니다.

Example

#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
   int count = 0; // answer
   if(!type) { // when type 0 query is asked
      for(int i = 0; i < n; i++) {
         if(arr[i] >= val)
            count++;
      }
   } else { // when type 1 query is asked
      for(int i = 0; i < n; i++) {
         if(arr[i] > val)
            count++;
      }
   }
   cout << count << "\n";
}
int main() {
   int ARR[] = { 10, 15, 30, 40, 45 };
   int n = sizeof(ARR)/sizeof(ARR[0]); // size of our array
   query(ARR, n, 0, 50); // query 1
   query(ARR, n, 1, 40); // query 2
   query(ARR, n, 0, 30); // query 3
   return 0;
}

Output

0
1
3

위의 방법에서는 배열을 반복하고 쿼리에 대한 답을 계산합니다. 이 방법은 주어진 예에 유효하지만 더 높은 제약 조건이 발생하면 이 방법은 실패합니다. 프로그램의 총 시간 복잡도는 O(N*Q)입니다. 여기서 N은 배열의 크기이고 Q는 쿼리 수이므로 이제 이 접근 방식을 더 높은 제약 조건에 맞게 최적화하겠습니다.

효율적인 방법

이 방법에서는 이진 검색을 사용하여 주어진 값의 상한과 하한을 찾습니다. 먼저 이진 검색을 사용하여 배열을 정렬한 다음 필요에 따라 하한 및 상한 함수를 적용합니다.

Example

#include <bits/stdc++.h>

using namespace std;
void lowerbound(int *arr, int n, int val) {
   int l = -1, r = n;
   while(r - l > 1) { // binary searching the answer
      int mid = (l+r)/2;
      if(arr[mid] >= val)
         r = mid;
      else
         l = mid;
   }
   if(r == n) // if r is unmoved then it means there is no element that satisfy the condition
      cout << "0\n";
   else
      cout << n - r << "\n";
}
void upperbound(int *arr, int n, int val) {
   int l = -1, r = n;
   while(r - l > 1) { // binary searching the answer
      int mid = (l+r)/2;
      if(arr[mid] > val)
         r = mid;
      else
         l = mid;
   }
   if(r == n)// if r is unmoved then it means there is no element that satisfy the condition
      cout << "0\n";
   else
      cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
   if(!type) // if type == 0 we call lower bound function
      lowerbound(arr, n, val);
   else // if type == 1 we call upperbound function
      upperbound(arr, n, val);
}
int main() {
   int arr[] = { 1, 2, 3, 4 };
   int n = sizeof(arr)/sizeof(arr[0]); // size of our array
   sort(arr, arr+n); // sorting the array
   query(arr, n, 0, 5); // query 1
   query(arr, n, 1, 3); // query 2
   query(arr, n, 0, 3); // query 3
   return 0;
}

Output

0
1
2

위 코드는 이진 검색을 사용하여 시간 복잡도를 크게 줄여줍니다. 따라서 최종 복잡도는 O(NlogN)입니다. 여기서 N은 배열의 크기입니다.

위 코드 설명

이 방법에서는 이진 검색을 사용하여 주어진 값의 상한과 하한을 찾습니다. 이제 이진 검색의 경우 정렬된 배열에서만 작동하므로 배열을 먼저 정렬합니다. 유형 0과 유형 1의 조건을 충족하는 첫 번째 숫자를 찾는 데 도움이 되는 하한 및 상한 함수를 만듭니다. 이제 배열이 정렬되었습니다. 조건을 만족하는 첫 번째 숫자를 찾았으므로 이 요소 다음의 요소도 조건을 충족하므로 해당 요소와 N 인덱스(배열의 크기) 간의 차이를 인쇄합니다.

결론

이 기사에서는 이진 검색을 사용하여 이상 및 이하 쿼리를 해결하는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하기 위한 완전한 접근 방식(사소하고 효율적인)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되었기를 바랍니다.

위 내용은 C++를 사용하여 보다 크거나 작지 않은 쿼리 작성의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!