알고리즘 - c++ lower_bound, upper_bound 활용하기
📌 lower_bound, upper_bound 란?
- c++에서는 이진 탐색으로 원소를 탐색하는 lower_bound, upper_bound 함수를 제공합니다.
lower_bound
- 용도 :
찾으려는 key 값보다 같거나 큰 숫자가배열 몇 번째에서 처음 등장하는지 찾기 위함 ⭐ 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함
- 사용법(배열)
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int arr[6] = { 1,2,3,4,5,6 };
cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr;
// 결과 -> lower_bound(6) : 5
return 0;
}
- arr 부터 끝까지 탐색하면서 6 이상의 숫자가 처음으로 나오는 위치의 인덱스 번호를 반환하는 예제입니다.
arr 배열에서
6은 0,1,2,…,5번째 인덱스에서 처음으로 등장합니다.- lower_bound의 반환형은 Iterator 이므로 실제로 몇 번째 인덱스인지 알고 싶다면, 위 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 됩니다.
벡터의 경우 아래와 같이 v.begin()을 빼 주면 됩니다.
- 사용법(벡터)
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr = { 1,2,3,4,5,6,6,6 };
cout << "lower_bound(6) : " << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();
// 결과 -> lower_bound(6) : 5
return 0;
}
upper_bound
- 용도 : 찾으려는 key 값을 초과하는 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위함
⭐ 사용 조건 : 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 함
- 사용법(배열도 위와 동일)
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr = { 1,2,3,4,5,6 };
cout << "upper_bound(3) : " << upper_bound(arr.begin(), arr.end(), 3) - arr.begin();
// 결과 -> upper_bound(3) : 3
return 0;
}
- 처음부터 끝까지 탐색하면서 3을 처음으로 초과하는 숫자가 나오는 위치의 인덱스 번호를 반환하는 예제입니다.
- 여기서 3을 처음으로 초과하는 숫자는 4 이며, 4는 벡터의 0,..2,
3번째에 위치해 있습니다. - 따라서 결과는 3이 출력됩니다.
🔑 이런 문제에서 활용할 수 있습니다
👆 오름차순 정렬된 자료에서 특정 범위에 속하는 숫자들이 몇 개 있는지 탐색하고자 할 때
이진 탐색 기반의 lower, upper_bound를 사용하면 시간 복잡도를 효과적으로 줄일 수 있습니다.
- (예)
{1,3,5,5,7,8,8,10,10,11,13}에서 5 이상 11 이하의 숫자가 몇 개인지 구할 때 - 아래와 같이 활용할 수 있습니다!
1
2
3
4
5
6
7
int main() {
vector<int> arr = { 1,3,5,5,7,8,8,10,10,11,13 };
cout << "5 이상 11 이하의 갯수 : " << upper_bound(arr.begin(), arr.end(), 11) - lower_bound(arr.begin(), arr.end(), 5);
return 0;
}
✌ 오름차순 정렬된 자료에서 특정한 숫자가 몇 번 나오는지 탐색하고자 할 때
- 이진 탐색 기반의 lower, upper_bound를 사용하여 O(logN)으로 탐색 가능합니다. O(N)이 불가능 할 때 유용하게 사용할 수 있습니다.
1
2
3
4
5
6
7
int main() {
vector<int> arr = { 1,3,5,5,5,8,8,10,10,11,13 };
cout << "5의 갯수 : " << upper_bound(arr.begin(), arr.end(), 5) - lower_bound(arr.begin(), arr.end(), 5);
return 0;
}
- 5보다 큰 숫자가 처음으로 나오는 위치 - 5 이상의 숫자가 처음으로 나오는 위치를 한 값입니다.
관련 문제