1. lower_bound와 upper_bound란?
lower_bound 와 upper_bound 는 바이너리 탐색 기법으로 정해진 구간 내에서 원소를 탐색하는 방법입니다.
첫째, lower_bound는 지정된 값보다 큰 첫 번째 주소입니다.
를 반환합니다.
둘째, upper_bound 는, 지정된 값보다 큰 값의 최초의 주소를 반환합니다.
바이너리 검색과 같은 중요한 점은 배열의 값은 오름차순으로 “정렬”되어야 합니다.
는 점입니다.
2. lower_bound 및 upper_bound 선언
이진 검색과 마찬가지로 algorithm 헤더 파일에 포함되어 있습니다.
인기글
algorithm 헤더 파일은 다음과 같이 선언합니다.
#include <algorithm>
lower_bound는 다음과 같이 선언합니다.
lower_bound(처음주소, 마지막주소, 값);
upper_bound는 다음과 같이 선언합니다.
upper_bound(처음주소, 마지막주소, 값);
3. lower_bound 및 upper_bound 사용
위와 같이 lower_bound 및 upper_bound는 “주소 값”을 반환합니다.
하지만 우리가 필요로 하는 값은 ‘주소 값’이 아니라 ‘인덱스’ 또는 ‘실제 값’입니다.
따라서 인덱스 값과 실제 값을 얻는 방법을 아는 것이 더 중요합니다.
lower_bound에서 보자.
우리가 지정된 값 이상의 첫 번째 인덱스 값필요한 경우 다음과 같이 사용할 수 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = { 1,2,3,4,5 };
cout << "index : " << lower_bound(vec.begin(), vec.end(), 3) - vec.begin();
//출력 값 -- index : 2
return 0;
}
upper_bound를 살펴보자.
우리가 정해진 값보다 큰 처음 인덱스 값필요한 경우 다음과 같이 사용할 수 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = { 1,2,3,4,5};
cout << "index : " << upper_bound(vec.begin(), vec.end(), 4) - vec.begin();
//출력 값 -- index : 4
return 0;
}
4. lower_bound 및 upper_bound 활용
이 두 STL 함수를 통해 지정된 구간 내의 특정 값의 수을 얻을 수 있습니다.
잘 이해하고 문제를 해결할 때 사용하면 매우 유용합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = { 1,2,3,4,5,6,7,7,7,7,7,8,8,9 };
cout << "7의 개수 : " << upper_bound(vec.begin(), vec.end(), 7) - lower_bound(vec.begin(), vec.end(), 7);
//출력 값 -- 7의 개수 : 5
return 0;
}
다음과 같이 특정 값의 범위도 정의할 수 있습니다.
(그러나 upper_bound의 값은 더 큰 값을 포함해야 합니다.
)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> vec = { 1,2,3,4,5,6,7,7,7,7,7,8,8,9 };
cout << "7부터 8의 개수 : " << upper_bound(vec.begin(), vec.end(), 8) - lower_bound(vec.begin(), vec.end(), 7);
//출력 값 -- 7부터 8의 개수 : 7
return 0;
}
그럼 예를 풀어 보겠습니다.
예를 들어, 먼저 풀어 보겠습니다.
예) 백준10816 번호카드2
<プール>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> vec1, vec2;
int n1, n2, i;
cin >> n1;
for (int a = 0; a < n1; a++)
{
cin >> i;
vec1.push_back(i);
}
sort(vec1.begin(), vec1.end());
cin >> n2;
for (int a = 0; a < n2; a++)
{
cin >> i;
cout << upper_bound(vec1.begin(), vec1.end(), i) - lower_bound(vec1.begin(), vec1.end(), i) << " ";
}
return 0;
}