Posts 알고리즘 - c++ lower_bound, upper_bound 활용하기
Post
Cancel

알고리즘 - c++ lower_bound, upper_bound 활용하기


알고리즘 - 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 이상의 숫자가 처음으로 나오는 위치를 한 값입니다.

관련 문제

[백준] 19237번 - 어른 상어(삼성 공채)

Google Analytics로 블로그 통계 확인하기(Google Anlytics, 네이버 애널리틱스)