[알고리즘] Lower bound, Upper bound

Lower bound

---

선형구조의 부분탐색법인 이분탐색은 찾고자 하는 값이 없으면(맨 마지막 값) 탐색 실패!

하지만,

lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치입니다. lower bound의 경우에는 같은 원소가 여러개 있더라도 상관없습니다. 찾고자 하는 값 이상의 값이 처음 나타나는 위치를 찾아내기 위해, 이분탐색 방법에서의 조건을 조금 변경하면 됩니다.

[문제] n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어 있으며(이분 탐색 가능), 같은 수가 여러개 존재할 수 있다.

입력) 첫 줄에 한 정수 n이 입력된다. 둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다. 셋째 줄에는 찾고자 하는 값 k가 입력된다. (단, 2 <= n <= 1,000,000, 각 원소의 크기는 100,000,000을 넘지 않는다.)

출력) 찾고자 하는 원소의 위치를 출력한다. 만약 모든 원소가 k보다 작으면 n+1을 출력한다.

입력 예	출력 예
5  1 3 5 7 7   7	4
8  1 2 3 5 7 9 11 15  6	5
5  1 2 3 4 5  7	6

해결방법) 먼저, 데이터가 입력되어있는 배열을 A[], 찾고자 하는 값을 k, lower bound를 찾고자 하는 구간을 [s, e]로 설정하면, 구간 내의 중간 위치를 m이라고 할때, A[m-1] < k이면서 A[m] >= k를 만족하는 최소 m을 찾는 문제가 된다.

1 3 5 7 7 에서 7을 탐색할 때, 7과 같거나 큰 수가 나오는 첫 위치가 바로 lower bound!

이때, m은 2이상인 값이 되는데, 일반적인 이분탐색 방법에서 A[m] == k인 부분을 포함시키면 된다.

또한, 모든 원소가 k보다 작을 때에는 n+1을 출력해야 하므로, 처음 구간을 잡을 때, [1, n]을 잡는 대신 [1, n+1]을 잡아야 한다.

데이터를 A[] 배열에 모두 입력 받은 상태에서 탐색 준비를 한다. 찾아야 할 데이터 k(6)와 같거나 큰 가장 첫 위치 lower bound, 탐색 구간의 시작위치와 마지막 위치는 s=0, e=7+1이 되고, 중간 위치를 계산하면 (0+8)/2 = 4가 된다.

A[4]의 값(7)이 찾고자 하는 6보다 크므로, 탐색 구간을 [0,4]로 바꾼다. 일반적인 이분탐색이었다면 탐색 구간을 [0,3]으로 바꿔야 하지만, lower bound는 k이상의 값이 나타나는 최소위치이므로, 마지막 위치 (e)까지 포함 시켜야 한다. [0,4]의 중간 위치는 (0+4)/2 = 2가 된다.

A[2]의 값(3)이 찾고자 하는 6보다 작으므로, 탐색 구간을 [3,4]로 바꾸고 다시 탐색해 나간다. [3, 4]의 중간 위치는 (3+4)/2=3이 된다.

이제 더이상 탐색 구간을 줄일 수 없으므로, 위치 4가 k이상인 원소의 최초 위치가 된다.

#include <stdio.h>
int n, k, A[1000001];
int solve(int s, int e) 
{
    int m;
    while(e-s > 0)
     {
        m = (s+e)/2;
        if(A[m] < k) s=m+1;
        else e = m;
    }
    return e+1;
}
int main() 
{
    scanf("%d", &n);
    for(int i=0; i < n; i++)
        scanf("%d", A+i);
    scanf("%d", &k);
    printf("%d\n", solve(0, n));
    return 0;
}

6: 주어진 범위 [s,e]에서 참색하도록 한다. s==e이면 반복 종료

8: 주어진 범위의 중간 위치를 계산한다.

9: 찾고자 하는 값보다 작으면 오른쪽으로 한 칸만 더 시작 구간 갱신

10: 찾고자 하는 값보다 크면 거기까지 끝 구간 갱신

12: 찾는 구간에 없는 경우 가장 마지막+1 위치 전달

lower_bound는 이분탐색과 비슷하지만 끝의 경계조건을 처리하기가 매우 까다롭습니다. 따라서 실제 정보올림피아드 대회에서는 lower_bound를 활용하기 위해서 stl라이브러리인 알고리즘에 포함된 함수를 사용합니다.

lower_bound(): <algorithm>에 포함되어있는 함수로, n개의 데이터로 채워진 A[] 배열에서 비교기준(compare)에 따라서 lower_bound의 위치를 계산해 줍니다.

std::lower_bound(A, A+n, k, [compare])

[compare] 부분을 생략하는 경우에는 기본적으로 오름차순으로 정렬한 상태라고 가정했을 때의 lower bound 위치를 계산해 줍니다.

#include <stdio.h>
#include <algorithm>

int n, k, A[1000001];

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", A+i);
    scanf("%d", &k);
    printf("%d\n", std::lower_bound(A, A+n, k)-A+1;
}

12: std::lower_bound(A, A+n, k)는 어떤 위치, std::lower_bound(A, A+n, k)-A+1은 A배열에서의 상대적 위치(인덱스)

Upper bound

---

lower bound는 찾고자 하는 값 이상이 처음으로 나타나는 위치인 반면에, upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치입니다.

입력 예	Lower bound	Upper Bound
5  1 3 5 7 7  7	4	6 ( 7을 초과한 값 )

[문제] n개로 이루어진 정수 집합에서 원하는 수 k를 초과하는 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어 있으며, 같은 수가 여러 개 존재할 수 있다.

입력) 첫 줄에 한 정수 n과 찾고자 하는 값 k가 공백으로 구분되어 입력되고, 둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다. (단, 2 <= n <= 1,000,000, 각 원소의 크기는 100,000,000을 넘지 않는다)

출력) 찾고자 하는 원소의 위치를 출력한다. 만약 모든 원소가 k보다 작으면 n+1을 출력한다.

입력 예	출력 예
5  1 3 5 7 7   7	5
8  1 2 3 5 7 9 11 15  6	7
5  1 2 3 4 5  7	6

해결방법) 먼저, 데이터가 입력되어있는 배열을 A[], 찾고자 하는 값을 k, upper bound를 찾고자 하는 구간을 [s,e]로 설정하면, 구간 내의 중간 위치를 m이라고 생각할 때, A[m-1] <= k 이면서 A[m]>k를 만족하는 최소 m을 찾는 문제가 된다.

1 3 5 7 7 에서 5를 탐색할 때, 5를 초과하는 첫 위치가 바로 upper bound!

이때, m은 2이상인 값이 되는데, 일반적인 이분탐색에서 A[m] == k인 부분을 포함시키면 된다. 또한, 모든 원소가 k보다 작을 때에는 n+1을 출력해야 하므로, 처음 구간을 잡을 때, [1, n]을 잡는 대신 [1, ㅜ+1]을 잡아야 한다.

데이터를 A[] 배열에 모두 입력 받은 상태에서 탐색 준비를 한다. 찾아야할 데이터 k(7)보다 큰 가장 첫 위치 upper bound, 탐색 구간의 시작위치와 마지막 위치는 s=0, e=7+1이 되고, 중간 위치를 계산하면 (0+8)/2 = 4가 된다.

A[4]의 값(7)이 찾고자 하는 7과 같으므로 탐색 구간을 [5, 8]로 바꾼다. 일반적인 이분탐색이었다면 바로 탐색을 종료해야 하지만, upper bound는 k를 초과하는 위치이므로 위치 4를 포함시킬 필요가 없다. [5,8]의 중간 위치는 (5+8)/2=6이 된다.

A[6]의 값(11)이 찾고자 하는 7보다 크므로 탐색 구간을 [5,6]으로 바꾸고 재탐색한다. [5,6]의 중간위치는 (5+6)/2=5가 된다. A[5]의 값(7)이 찾고자 하는 7과 같으므로 탐색 구간을 [6,6]으로 바꾸고 재탐색 한다. [6,6]의 중간위치는 (6+6)/2=6이 된다.

[6,6]의 범위는 더 이상 탐색할 필요가 없으므로, 6번의 위치가 upper bound라는 것을 판단할 수 있다.

int solve(int s, int e)
{
    int m;
    while(e-s > 0)
    {
        m = (s+e)/2;
        if(A[m] <= k) s=m+1;
        else e=m;
    }
    return e+1;
}

4: 주어진 범위 [s,e]에서 탐색하도록 한다. s==e이면 반복 종료

6: 주어진 범위의 중간 위치를 계산한다.

7: 찾고자 하는 값보다 작거나 같으면 오른쪽으로 한 칸 더 시작 구간 갱신(lower bound에서는 A[m]<k)

12: 찾고자 하는 값보다 크면 거기까지 끝 구간 갱신

14: 찾는 구간에 없는 경우 가장 마지막+1 위치 전달

Upper_bound(): <algorithm>에 포함되어있는 함수로, n개의 데이터로 채우진 A[] 배열에서 비교기준(compare)에 따라서 Upper_bound의 위치를 계산해 준다.

std::upper_bound(A, A+n, k, [compare])

[compare] 부분을 생략하는 경우에는 기본적으로 오름차순으로 정렬한 상태라고 가정했을 때의 upper bound 위치를 계산해 준다.

#include <stdio.h>
#include <algorithm>

int n, k, A[1000001];

int main()
{
    scanf("%d", &n);
    for(int i=0; i<n; i++)
        scanf("%d", A+i);
    scanf("%d", &k);
    printf("%d\n", std::upper_bound(A, A+n, k)-A+1);
}

12: std::upper_bound(Am A+n, k)는 어떤 위치, std::upper_bound(A, A+n, k)-A+1은 A 배열에서의 상대적 위치(인덱스)

lower bound는 정렬되어있는 데이터 집합에서 k값 이상이 처음발견되는 위치를 의미하고, upper bound는 k값을 초과하는 값이 처음 발견되는 위치를 의미합니다.