상한 : 찾고자 하는 특정 값을 초과하는 '첫 위치' 반환
하한 : 찾고자 하는 특정 값 이상인 '첫 위치' 반환
-> 중복 값이 있을 때의 활용
arr1{1, 2, 2, 2, 3} 일 때 Key 값이 2이고, Upper Bound로 찾는다면 2를 초과되는 처음 위치인 arr[4] = 3인 index 4 반환
Lower Bound로 찾게 된다면 2 이상 위치 중 처음 위치인 arr[1] = 2인 index 1 반환
중복 원소에서 가장 끝 값(가장 오른쪽 값)을 찾고자 한다면 Upper Bound - 1
중복 원소 중 가장 왼쪽 끝 값(가장 왼쪽 값)을 찾고자 한다면 Lower Bound 그대로
private static int lowerBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
// lo가 hi랑 같아질 때 까지 반복
while (lo < hi) {
int mid = (lo + hi) / 2; // 중간위치를 구한다.
/*
* key 값이 중간 위치의 값보다 작거나 같을 경우
*
* (중복 원소에 대해 왼쪽으로 탐색하도록 상계를 내린다.)
*/
if (key <= arr[mid]) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return lo;
}
private static int upperBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
// lo가 hi랑 같아질 때 까지 반복
while (lo < hi) {
int mid = (lo + hi) / 2; // 중간위치를 구한다.
// key값이 중간 위치의 값보다 작을 경우
if (key < arr[mid]) {
hi = mid;
}
// 중복원소의 경우 else에서 처리된다.
else {
lo = mid + 1;
}
}
return lo;
}
예시 - 백준 랜선 자르기 (1654)
// min = 0, max 는 입력받은 LAN선 중 가장 긴 길이를 갖는다.
while (min < max) {
// 범위 내에서 중간 길이를 구한다.
mid = (max + min) / 2;
long count = 0;
// 구해진 중간 길이로 잘라서 총 몇 개가 만들어지는지를 구한다.
for (int i = 0; j < arr.length; i++) {
count += (arr[i] / mid);
}
/*
* [upper bound 형식]
*
* mid길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면
* 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
* 그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
*/
if(count < N) {
max = mid;
}
else {
min = mid + 1;
}
}
c++은 라이브러리 제공 - 벡터/배열 오름차순 정렬되어있어야 함
#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;
}
'algorithm > 정리' 카테고리의 다른 글
그리디 알고리즘 (0) | 2024.04.09 |
---|---|
DP (다이나믹 프로그래밍) (0) | 2024.04.08 |
이분탐색 (0) | 2024.04.05 |
99클럽 코테 스터디 5일차 TIL - 자바 map 관련 함수 (getOrDefault, equals) (1) | 2024.04.05 |
정렬 알고리즘 (거품, 선택, 삽입, 퀵, 병합, 힙, 계수 정렬) (0) | 2024.04.04 |