지난번에도 언급한거 같긴 한데.. 기초가 많이 부족하다.
빠르게 기초를 뿌셔보자
📌 Lower Bound
🙄 lower Bound? 낮은 경계? 경계를 타깃값으로 생각했을 때 낮은 값이라는 의미인가
라는 생각을 난 먼저 했다.
일단 아님‼️‼️‼️‼️ 혹시나 저 말 때문에 헷갈리지 않았으면 좋겠다.
난 저 말 때문에 계속 헤맸기에 혹시나 같은 생각을 하는 사람들이 있다면 아니라고 일러주고 싶어서 적었다.
저 해석은 부분적으로는 맞는 말이다.
아래 이미지처럼 45가 세개 있다면, 타깃값을 경계라고 여겼을 때 가장 작은 값이 45이기 때문이다.
하지만 타깃값이 배열에 존재하지 않는다면, 예를 들어 49라는 값을 찾는다면 lower bound는 57이 된다.
lower bound의 정의는 target 이상의 값이 처음으로 나오는 위치이다.
즉, 타겟값과 같거나, 큰 원소 중 가장 작은 값이 나오는 위치이다.
이때, 이상이라는 말에 주의해야한다.
타겟값을 포함한 개념이 Lower bound이다.
🔍 구현
위에서 말한 이상 이라는 개념에 주의해야 한다.
public int lowerBound(int arr[], int target){
int left = 0;
int right = arr.size-1;
int minIndex = arr.size;
while(left <= right){
mid = (left+right) / 2;
if(arr[mid] >= target){
minIndex = Math.min(mid, minIndex)
right = mid-1;
}else{
left = mid+1;
}
}
return minIndex;
}위 코드를 보면
if(arr[mid] >= target)
이라는 부분이 존재한다. 이부분이 타깃 이상 값을 처리하기 위한 부분이다.
📌 Upper Bound
이제 Upper bound다.
아마 반대 의미를 지니고 있는 만큼 아예 반대 개념인가 할 수 있는데 엄청 유사한 개념이다.
원하는 값 target을 초과하는 값이 최초로 나오는 위치
이게 upper bound의 정의이다.
따라서 위에서 봤던 이미지를 다시 사용하여 upper bound에 대해 정의하자면,
45의 upper bound와 49의 upper bound가 동일함을 알 수 있다.
🔍 구현
여기서는 이상이 아니라 초과라는 표현을 썼다.
결국 위의 코드에서 if(arr[mid] > target) 로만 바꿔주면, 타깃값 초과인 경우를 반환할 수 있게 된다.
그래도 전체 코드가 없으면 섭하니 넣어주겠다.
public int upperBound(int arr[], int target){
int left = 0;
int right = arr.size-1;
int minIndex = arr.size;
while(left <= right){
mid = (left+right) / 2;
if(arr[mid] > target){
minIndex = Math.min(mid, minIndex)
right = mid-1;
}else{
left = mid+1;
}
}
return minIndex;
}🤔 사용방법?
약간 감이 오는 사람도 있을거다!
lower bound와 upper bound 사이에 어떤 값이 들어가는지 생각해보자.
내가 원하는 타깃값이 사이에 들어감을 쉽게 알 수 있다!
따라서
Upper bound - Lower bound = target 값의 수
즉 타깃값이 없으면 결과가 0이 나옴을 알 수 있다.
이걸 사용해서 배열에서 내가 찾는 값이 있는지 확인 가능하다!
📌 시간복잡도는?
둘다 이진탐색이다! 당연히 각각
출처
(당분간은 죄다 코드트리일 예정!)
https://www.codetree.ai/missions/6/problems/lower-upper/introduction
.jpeg)