C++로 알고리즘 문제를 풀다보면 upper_bound, lower_bound를 사용해 쉽게 풀 수 있는 문제를 자주 만날 수 있다.
upper_bound, lower_bound를 사용할 때마다 구글링해서 '아 맞다 이거였지' 하는 내 스스로가 조금 ... 별로인 것 같아 글로 정리한다.

공식문서 개념

upper_bound

메서드 정의

<algorithm> 헤더 파일에 들어있는 메서드이다.
정렬된 범위에서 지정된 값보다 큰 값을 가진 첫 번째 요소의 위치를 찾는 메서드이다.

template<class ForwardIterator, class Type>
ForwardIterator upper_bound(
    ForwardIterator first,
    ForwardIterator last,
    const Type& value);

파라미터

first : 검색할 범위에서 첫 번째 요소의 위치를 지정하는 순방향 이터레이터
last : 검색할 범위의 마지막 요소에서 한 단계 지난 위치를 지정하는 순방향 이터레이터
value : 이터레이터가 반환한 요소의 값을 초과해야 하는 정렬된 범위의 값

반환값

지정된 값보다 큰 값을 가진 첫 번째 요소의 위치에 대한 순방향 이터레이터를 반환한다.

lower_bound

메서드 정의

<algorithm> 헤더 파일에 들어있는 메서드이다.
지정된 값보다 크거나 같은 값을 가진 정렬된 범위에서 첫 번째 요소의 위치를 찾는 메서드이다.

template<class ForwardIterator, class Type>
ForwardIterator lower_bound(
    ForwardIterator first,
    ForwardIterator last,
    const Type& value );

파라미터

first : 검색할 범위에서 첫 번째 요소의 위치를 지정하는 순방향 이터레이터
last : 검색할 범위의 마지막 요소에서 한 단계 지난 위치를 지정하는 순방향 이터레이터
value : 정렬된 범위에서 첫 번째 위치 또는 가능한 첫 번째 위치가 검색되는 값

반환값

지정된 값보다 크거나 같은 값을 가진 정렬된 범위의 첫 번재 요소 위치에 있는 순방향 이터레이터를 반환한다.

좀 더 쉽게 설명해주면 안 될까 ?

upper_bound, lower_bound 쉬운 설명

upper_bound, lower_bound는 <algorithm> 헤더 파일 안에 있는 메서드이다.

이 메서드는 어떨 때 활용하는 메서드일까 ?

바로 '정렬된 리스트 안에서 특정 값 이상(lower_bound), 초과(upper_bound)하는 원소의 이터레이터를 쉽고 빠르게 찾고자 할 때' 사용한다.

lower_bound, upper_bound라는 단어 자체를 보면, bound, 즉 경계이다.
그런데 이 경계가 upper, 즉 특정 기준을 초과하는지, 혹은 lower, 특정 기준 이상이기만 하면 되는지를 나타내는 것이다.

비교적 쉬운 개념인데, 평소에 자주 사용하는 메서드가 아니다 보니 종종 까먹고 매번 구글링을 하는 것 같다.

사용 방법

일반적인 경험을 보태어 문제를 생각해보겠다.

6명의 참가자가 있다.
그리고 이 참가자들이 획득한 점수가 있다.
예를 들어 아래와 같다.

• 1번 참가자 - 1점
• 2번 참가자 - 2점
• 3번 참가자 - 3점
• 4번 참가자 - 3점
• 5번 참가자 - 4점
• 6번 참가자 - 5점

점수가 낮을수록 순위가 높다고 하자.
1번 참가자가 1위, 2번 참가자가 2위, 3번, 4번 참가자가 공동 3위, 5번 참가자가 5위, 6번 참가자가 6위인 셈이다.

1번 ~ 6번 중 어떤 참가자의 점수 v가 주어진다.
이 v를 점수로 가진 참가자는 전체 중 몇 위일까 ?

가장 단순한 풀이법을 생각해보면, 참가자들의 점수를 정렬한 후 순차적으로 탐색하며 v보다 크거나 같은 원소를 가진 인덱스 + 1을 한 값이 구하고자 하는 순위가 될 것이다.

이런 문제를 lower_bound를 사용해 아래와 같이 쉽게 풀 수 있다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
   // sorted array
   int arr[6] = {1, 2, 3, 3, 4, 5};

   cout << "lower bound(index) for 3 : " << lower_bound(arr, arr + 6, 3) - arr + 1 << "\n";
   // printed : "lower bound(index) for 3 : 3"

   return 0;
}

위 코드에서 lower_bound를 사용해 문제를 해결했다.
lower_bound는 value로 전달된 값보다 크거나 같은 값이 처음 나온 원소의 이터레이터를 반환한다.

upper_bound의 경우는 value로 전달된 값보다 큰, 즉 초과하는 원소의 이터레이터를 반환한다.

사용 시 주의사항

만약 위 예시 코드에서 arr가 정렬되지 않았다면 어떤 상황이 생길까 ?

arr의 순서를 조금 바꿔보았다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
   // sorted array
   int arr[6] = {1, 4, 2, 3, 3, 5};

   cout << "lower bound(index) for 3 : " << lower_bound(arr, arr + 6, 3) - arr + 1 << "\n";
   // printed : "lower bound(index) for 3 : 2"

   return 0;
}

저 6명의 참가자 중, 3점을 획득한 사람의 순위는 3위여야 하는 것은 변함이 없다.

하지만 정렬되지 않은 리스트에 lower_bound(혹은 upper_bound)를 사용하게 된다면, 우리가 원하는 '3' 이라는 값이 아니라 '2' 라는 값이 반환된다.

여기서 lower_bound, upper_bound를 사용할 때에는 꼭 정렬된 리스트에서 사용해야 한다는 점을 알 수 있다.

그렇다면 정렬된 리스트에서 사용해야 하는 이유는 무엇일까 ?

lower_bound, upper_bound 동작 원리

두 메서드는 이분 탐색을 기반으로 동작한다.

이 글에서 이분 탐색에 대해 깊게 다루지는 않을 것이다(왜냐면 이 글은 이분 탐색에 대해 알아보기 위해 쓴 글이 아니기 때문이다 ... 이분 탐색이 뭔지 모르겠다면 다른 블로그 글들을 찾아보는 것을 추천 ... 한다. 죄송하다).

이분 탐색은 기본적으로 정렬된 리스트에 대해 적용할 수 있는 탐색 기법이기 때문에, lower_bound, upper_bound 메서드 역시 정렬된 리스트에 대해 수행되어야 한다.

lower_bound와 upper_bound는 '이상, 초과' 라는 차이 뿐이니, lower_bound를 기준으로 설명한다.

lower_bound는 기본적으로 아래 순서에 따라 진행된다.

1. lower_bound 메서드는 파라미터로 두 개의 이터레이터(first, last)와 검색할 값(value)을 사용한다.
2. last에서 first를 빼 범위의 길이를 계산한다.
3. 두 변수를 초기화한다 : 시작 위치로 first, 끝 위치로 last
4. 범위의 길이가 0보다 큰 동안, 반복문을 수행한다.
5. 루프 내부에서 first에 범위 길이의 절반을 더해 중간 이터레이터를 계산한다.
6. 중간 이터레이터가 가리키는 값과 주어진 값(value)을 비교한다.
7. 중간 이터레이터의 값이 주어진 값보다 작으면, first를 중간 이터레이터 + 1의 값으로 설정한다.
8. 중간 이터레이터의 값이 주어진 값보다 크거나 같으면, last를 중간 이터레이터 값으로 설정한다.
9. 루프 후 lower_bound 메서드는 주어진 값보다 작지 않은(크거나 같은) 첫 번째 요소를 가리키는 first를 반환한다.

이에 따라, 위 예시였던 arr[6] = {1, 4, 2, 3, 3, 5} 에 대한 lower_bound가 왜 이상한 값을 반환하게 되었는지를 살펴보겠다.

• 첫 번째 루프
  • first -> arr[0]의 주소값, last -> arr[5]의 다음 주소값, 범위의 길이 = 6, value = 3인 상황
  • 중간 이터레이터는 arr[3]의 주소값을 가리킨다.
  • arr[3] = 3 이므로 value보다 크거나 같고, 따라서 last를 중간 이터레이터 값으로 설정하게 되므로 last -> arr[3]의 주소값을 가리키게 된다.
• 두 번째 루프
  • first -> arr[0]의 주소값, last -> arr[3]의 주소값, 범위의 길이 = 3, value = 3인 상황
  • 중간 이터레이터는 arr[1]의 주소값을 가리킨다.
  • arr[1] = 4 이므로 value보다 크거나 같고, 따라서 last를 중간 이터레이터 값으로 설정하게 되므로 last -> arr[1]의 주소값을 가리키게 된다.
• 세 번째 루프
  • first -> arr[0]의 주소값, last -> arr[1]의 주소값, 범위의 길이 = 1, value = 3인 상황
  • 중간 이터레이터는 arr[0]의 주소값을 가리킨다.
  • arr[0] = 1 이므로 value보다 작고, 따라서 first를 중간 이터레이터 + 1의 값으로 설정하게 되므로 first -> arr[1]의 주소값을 가리키게 된다.
• 네 번째 루프
  • first -> arr[1]의 주소값, last -> arr[1]의 주소값, 범위의 길이 = 0, value = 3인 상황
  • 범위의 길이가 0이므로 루프를 멈춘다.
• 따라서 lower_bound는 arr[1]의 주소값을 반환하게 되고, 위 코드에서는 (arr + 1) - (arr) + 1을 하게 되므로 2라는 값이 반환되게 된다.

이상으로 lower_bound, upper_bound에 대한 탐구를 마치도록 하겠다 !