이 글에서는 배열이 주어졌을 때 두 가지 유형의 쿼리에 답해야 하는 문제를 다룹니다.
- Type 0 — 주어진 값 x보다 크거나 같은(≥) 요소의 개수를 구합니다.
- Type 1 — 주어진 값 x보다 엄격하게 큰(>) 요소의 개수를 구합니다.
간단한 예시를 통해 살펴보겠습니다.
입력 : arr[] = { 10, 15, 30, 40, 45 }, Q = 3
쿼리 1 : 0 50
쿼리 2 : 1 40
쿼리 3 : 0 30
출력 :
0
1
3
설명:
x = 50, q = 0 : 50 이상인 요소는 없습니다.
x = 40, q = 1 : 45가 40보다 큽니다.
x = 30, q = 0 : 30, 40, 45 세 개의 요소가 30 이상입니다.문제 해결 접근 방식
이 문제는 두 가지 방법으로 풀 수 있습니다. 먼저 무식하게 모든 경우를 확인하는 브루트 포스(Brute Force) 방식으로 해결한 뒤, 더 큰 입력 제약 조건에서도 동작하는지 살펴봅니다. 만약 그렇지 않다면, 솔루션을 최적화하는 단계로 넘어갑니다.
브루트 포스 접근 방식
이 방식에서는 각 q개의 쿼리마다 배열 전체를 순회하면서 주어진 조건을 만족하는 숫자의 개수를 직접 세는 방법을 사용합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
int count = 0; // 정답
if(!type) { // type 0 쿼리인 경우
for(int i = 0; i < n; i++) {
if(arr[i] >= val)
count++;
}
} else { // type 1 쿼리인 경우
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]); // 배열의 크기
query(ARR, n, 0, 50); // 쿼리 1
query(ARR, n, 1, 40); // 쿼리 2
query(ARR, n, 0, 30); // 쿼리 3
return 0;
}
출력 결과
0
1
3
위 방식은 단순히 배열을 순회하며 각 쿼리에 대한 답을 계산합니다. 주어진 예제에서는 잘 동작하지만, 입력 제약 조건이 커지면 문제가 발생합니다. 이 프로그램의 전체 시간 복잡도는 O(N×Q)이며(N은 배열의 크기, Q는 쿼리의 개수), 따라서 더 큰 제약 조건에서도 동작할 수 있도록 최적화해야 합니다.
효율적인 접근 방식
이번에는 이분 탐색(Binary Search)을 활용해 주어진 값의 상계(upper bound)와 하계(lower bound)를 찾는 방법을 사용합니다. 먼저 배열을 오름차순으로 정렬한 후, lower bound와 upper bound 함수를 상황에 맞게 적용합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void lowerbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // 이분 탐색으로 정답 위치 찾기
int mid = (l+r)/2;
if(arr[mid] >= val)
r = mid;
else
l = mid;
}
if(r == n) // r이 그대로라면 조건을 만족하는 요소가 없다는 의미
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) { // 이분 탐색으로 정답 위치 찾기
int mid = (l+r)/2;
if(arr[mid] > val)
r = mid;
else
l = mid;
}
if(r == n) // r이 그대로라면 조건을 만족하는 요소가 없다는 의미
cout << "0\n";
else
cout << n - r << "\n";
}
void query(int *arr, int n, int type, int val) {
if(!type) // type == 0이면 lower bound 함수 호출
lowerbound(arr, n, val);
else // type == 1이면 upper bound 함수 호출
upperbound(arr, n, val);
}
int main() {
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr)/sizeof(arr[0]); // 배열의 크기
sort(arr, arr+n); // 배열 정렬
query(arr, n, 0, 5); // 쿼리 1
query(arr, n, 1, 3); // 쿼리 2
query(arr, n, 0, 3); // 쿼리 3
return 0;
}
출력 결과
0
1
2
위 코드는 이분 탐색을 사용하여 시간 복잡도를 크게 줄입니다. 최종 시간 복잡도는 O(NlogN)이 되며, 여기서 N은 배열의 크기를 의미합니다.
코드 설명
이 접근 방식에서는 이분 탐색을 통해 주어진 값의 upper bound와 lower bound를 찾습니다. 이분 탐색은 정렬된 배열에서만 동작하기 때문에 먼저 배열을 오름차순으로 정렬합니다. 이후 type 0, type 1 조건을 각각 처음으로 만족하는 숫자의 위치를 찾아주는 lower bound 함수와 upper bound 함수를 구현합니다. 배열이 정렬되어 있으므로, 조건을 처음 만족하는 원소를 찾으면 그 뒤에 있는 모든 원소 역시 조건을 만족합니다. 따라서 해당 원소의 인덱스와 N(배열의 크기)의 차이를 출력하면 됩니다.
결론
이 글에서는 이분 탐색(Binary Search)을 활용해 'x 이상' 및 'x 초과' 요소 개수를 묻는 쿼리 문제를 해결했습니다. 또한 이 문제에 대한 C++ 프로그램과 일반적인 방식(브루트 포스)과 효율적인 방식(이분 탐색)의 완전한 풀이 과정을 함께 살펴보았습니다. 동일한 프로그램은 C, Java, Python 등 다른 언어로도 작성할 수 있습니다. 이 글이 여러분께 도움이 되었기를 바랍니다.