[C++] lower_bound & upper_bound

STL에서 제공하는 lower_bound와 upper_bound에 대해서 알아보자. 

 

LIS(Longest Increasing Subsequence)를 공부하다가 알게 된 개념이다. 

 

필자 개인적으로는 STL에 대해서 잘 몰랐는데, 처음으로 STL이 매우 유용하다는 것을 깨닫게 해준 함수이다. 

(이를 계기로 계속 STL을 이용하려고 노력중이다)

 

우선 lower_bound와 upper_bound는 이진 탐색(Binary Search)을 기반으로 탐색하는 함수이다. 

따라서 배열이나 리스트, 벡터 등이 기본적으로 정렬이 되어있어야 하고, 시간복잡도는 O(logn)이다.

기본적으로 이진 탐색은 찾고자 하는 원소가 있는지, 있다면 어디에 위치해 있는지를 찾는다면,

lower_bound와 upper_bound는 이진 탐색을 바탕으로 원소가 어느 부분에 속할 수 있는지를 알려주는 함수이다.   

 

lower_bound와 upper_bound는 STL에 다음과 같이 선언되어있다. 이 함수들을 이용하기 위해서는 <algorithm> 헤더를 추가해야 한다. 

 

template <class ForwardIt, class T>
ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& val);
ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& val);
 
template <class ForwardIt, class T, class Compare>
ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& val, Compare cmp);
ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& val, Compare cmp);

 

lower_bound는 [first, last)의 범위에서 val보다 '크거나 같은' 원소 들 중 첫 번째 원소의 Iterator, 배열인 경우에는 원소의 주솟값이 반환 된다.  

쉽게 말해서, 처음으로 val 이상의 값이 나오는 위치를 반환한다.

만약에 val보다 모두 작다면 마지막 원소 다음의 위치를 반환해준다. 

 

upper_bound는 [first, last)의 범위에서 val보다 '큰' 원소 들 중 첫 번째 원소의 Iterator, 배열인 경우에는 원소의 주소값이 반환 된다. 

쉽게 말해서, 처음으로 val보다 큰 값이 나오는 위치를 반환한다. 

 

compare 함수를 이용하지 않으면 기본적으로 (default) '<' 연산자를 이용한다. 

즉, 오름차순으로 정렬되어 있는 경우에서 이용하는 것이다. 

compare 함수를 이용한다면 다른 상황에서도 lower_bound와 upper_bound함수를 이용할 수 있을 것이다. 

 

예시들을 통해서 쉽게 이해해보자.

(기본적으로 오름차순 정렬이 되어있다는 가정)

 

[배열(Array) 이용]

 

예시 1)

#include<iostream>
#include<algorithm>
#include<functional>
 
using namespace std;
 
int main(void) {
    int arr[10] = { 1, 3, 3, 4, 5, 6, 6, 8, 9, 10 };
    cout <<"주소 : " << lower_bound(arr, arr + 10, 2) <<'\n';
    cout <<"index : "<< lower_bound(arr, arr + 10, 2) - arr << '\n';
}

 

위의 예시는 arr 배열에서 val = 2인 경우이며, 원소들 중에서 처음으로 2 이상의 값이 나오는 index는 1이다. 

이처럼, lower_bound와 upper_bound함수는 해당 원소의 위치를 나타내는 주소값을 반환하므로,

실제 index를 구하기 위해서는 배열의 첫번째 원소의 주소값을 빼주면 된다. 

 

예시 2)

#include<iostream>
#include<algorithm>
#include<functional>
 
using namespace std;
 
int main(void) {
    int arr[10] = { 1, 3, 3, 4, 5, 6, 6, 8, 9, 10 };
    cout << "index : " << lower_bound(arr, arr + 10, 0) - arr << '\n';
    cout << "index : " << lower_bound(arr, arr + 10, 2) - arr << '\n';
    cout << "index : " << lower_bound(arr, arr + 10, 3) - arr << '\n';
    cout << "index : " << lower_bound(arr, arr + 10, 7) - arr << '\n';
    cout << "index : " << lower_bound(arr, arr + 10, 9) - arr << '\n';
    cout << "index : " << lower_bound(arr, arr + 10, 10) - arr << '\n';
    cout << "index : " << lower_bound(arr, arr + 10, 11) - arr << '\n';
 
    int val = 7;
    arr[lower_bound(arr, arr + 10, val) - arr] = val;
 
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';
}

 

18번째 줄은 val(7) 이상의 값 중 첫번째 원소의 index를 찾아 해당 index에 val을 할당해주는 부분이다. 

기본적으로 정렬되어 있는 상황에서 정렬을 유지하면서 어떤 원소를 추가하거나 교체할 때 이와 같이 이용해주면 된다. 

 

예시 3)

#include<iostream>
#include<algorithm>
#include<functional>
 
using namespace std;
 
int main(void) {
    int arr[10] = { 1, 3, 3, 4, 5, 6, 6, 8, 9, 10 };
    cout << "index : " << upper_bound(arr, arr + 10, 0) - arr << '\n';
    cout << "index : " << upper_bound(arr, arr + 10, 2) - arr << '\n';
    cout << "index : " << upper_bound(arr, arr + 10, 3) - arr << '\n';
    cout << "index : " << upper_bound(arr, arr + 10, 7) - arr << '\n';
    cout << "index : " << upper_bound(arr, arr + 10, 9) - arr << '\n';
    cout << "index : " << upper_bound(arr, arr + 10, 10) - arr << '\n';
    cout << "index : " << upper_bound(arr, arr + 10, 11) - arr << '\n';
 
    int val = 7;
    arr[upper_bound(arr, arr + 10, val) - arr] = val;
 
    for (int i = 0; i < 10; i++) cout << arr[i] << ' ';
}

 

upper_bound는 lower_bound와 이용 방법은 크게 차이가 없어 예시만 봐도 충분히 이해가 될 것 같다. 

 

[벡터(vector) 이용]

 

아직 vector에 익숙하지는 않지만, 연습 겸 vector를 이용한 예시도 한번 해보았다.

 

#include<iostream>
#include<algorithm>
#include<functional>
#include<vector>
 
using namespace std;
 
int main(void) {
    int arr[10] = { 1, 3, 3, 4, 5, 6, 6, 8, 9, 10 };
    vector<int> v(arr, arr + 10);
    
    cout << "index : " << lower_bound(v.begin(), v.end(), 0) - v.begin() << '\n';
    cout << "index : " << lower_bound(v.begin(), v.end(), 2) - v.begin() << '\n';
    cout << "index : " << lower_bound(v.begin(), v.end(), 3) - v.begin() << '\n';
    cout << "index : " << lower_bound(v.begin(), v.end(), 7) - v.begin() << '\n';
    cout << "index : " << lower_bound(v.begin(), v.end(), 9) - v.begin() << '\n';
    cout << "index : " << lower_bound(v.begin(), v.end(), 10) - v.begin() << '\n';
    cout << "index : " << lower_bound(v.begin(), v.end(), 11) - v.begin() << '\n';
 
    int val = 7;
    v[lower_bound(v.begin(), v.end(), val) - v.begin()] = val;
    for (int i = 0; i < 10; i++) cout << v[i] << ' ';
}

 

이를 이용하여 LIS 문제를 훨씬 간단하게 풀어낼 수 있다. 

LIS (Longest Increasing Subsequence) 

https://wogud6792.tistory.com/33

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열