컴공댕이 공부일지
[ 이분탐색🚩] 개념 + 활용 문제 ( 백준 c++ 1920 수 찾기 / 10816 숫자 카드 2 ) #UpperBound #LowerBound 본문
[ 이분탐색🚩] 개념 + 활용 문제 ( 백준 c++ 1920 수 찾기 / 10816 숫자 카드 2 ) #UpperBound #LowerBound
은솜솜솜 2023. 11. 6. 18:152023. 11. 3 일자 이화여대 알고리즘 튜터링 프로그램, 알튜비튜의 수업 내용 정리본입니다.
🔍이분 탐색 ( BinarySearch )이란 ?
업다운 게임을 생각하면 된다 !
중간값과 찾아야하는 값을 비교해가며,
배열의 크기를 절반으로 줄이며 답을 찾는 알고리즘으로
반복문으로 구현하며, 시간 복잡도는 O(logN)
알고리즘 사용 전, 반드시 배열을 정렬해야 한다 !!
+) 이분 탐색의 대상 원소들을 트리에 넣으면 바이너리서치트리(binary search tree) !
BST를 중위 순회 (inorder) 하면 정렬된 순서의 배열이 나온다.
배열의 원소가 정렬된 상태라면, 특정 원소를 찾는 여러 방법들 중 이분 탐색이 가장 빠르다 !!
이분탐색은 분할 정복과 달리 답이 없는 문제부(절반)은 아예 버림 !
📌 코딩 테스트 관련 Tip 📝
- 주로 Parametric search 문제로 출제됨
- 최댓값, 최솟값 키워드가 보이면, 이분 탐색을 의심하자 !
- 효율성 테스트 문제로도 아주 많이 출제됨
🔽 이분탐색 활용해 푸는 문제 🔽
백준 1920 수 찾기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//이분 탐색으로 배열에 key값이 있으면 1, 없으면 0 리턴
int BinarySearch(int key, const vector<int> &arr, int n) {
int left = 0;
int right = arr.size() - 1;
int mid ;
while(left <= right) {
mid = (left+right)/2;
if(arr[mid] == key) {
return 1;
} else if(arr[mid] < key) { //오른쪽으로
left = mid + 1;
} else { //왼쪽으로
right = mid -1;
}
}
return 0;
}
int main()
{
//속도 향상 코드
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(NULL);
int n,m,t;
vector <int> arr;
cin >> n;
while(n--) {
cin >> t ;
arr.push_back(t);
}
//이분탐색은 우선, 정렬 필수 !!
sort(arr.begin(), arr.end());
cin >> m ;
while(m--) {
cin >> t;
cout << BinarySearch(t, arr, n) << '\n';
}
return 0;
}
다음으로 풀어볼 문제는 위에서 활용했던 이분 탐색을 살짝 변형한 문제
단순 존재 여부만 판단한 위의 문제와 달리 이 문제는 '존재하는 개수'를 물어본다.
이 때 나오는 Upper Bound, Lower Bound 개념 !
Lower bound는 타겟값의 시작 위치를 찾는 알고리즘,
Upper bound는 타겟값이 처음 초과된 위치를 찾는 알고리즘이다.
이미지 출처: http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html
두 가지의 바운드 알고리즘은 이분 탐색을 기반으로 한다.
조금 다른 점은, 이분 탐색은 mid값이 찾고자 하는 타겟값과 같을 때 바로 리턴을 했다면,
위의 두 알고리즘은 mid 값이 타겟값과 같아져도 한 단계 더 의심을 한다.
왼쪽으로 혹은 오른쪽으로 더 가도 타겟값이 또 나오지 않을까? 하는 의심을 해보며,한 칸 더 나아가보는 것이다.
아래의 구현을 보면 이해가 될 것이다.
백준 10816 숫자카드 2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//lower bound (타겟이 처음으로 나온 위치) 찾기
int lowerBound(int key, const vector<int> &arr, int n) {
int left = 0;
int right = arr.size() - 1;
int mid ;
while(left <= right) {
mid = (left+right)/2;
if(arr[mid] < key) {
left = mid + 1;
} else { //왼쪽으로
right = mid -1;
//키값 찾아도 (mid == key) 일단 의심하며 왼쪽으로 더 가보기 !
}
}
return left;
}
//upper bound (타겟이 처음으로 초과된 위치) 찾기
int upperBound(int key, const vector<int> &arr, int n) {
int left = 0;
int right = arr.size() - 1;
int mid ;
while(left <= right) {
mid = (left+right)/2;
if(arr[mid] <= key) {
left = mid + 1;
//키값 찾아도 (mid == key) 일단 의심하며 오른쪽으로 더 가보기 !
} else { //왼쪽으로
right = mid -1;
}
}
return left;
}
int main()
{
cin.tie(0); cout.tie(0);
ios_base::sync_with_stdio(NULL);
int n,m,t;
vector <int> arr;
cin >> n;
while(n--) {
cin >> t ;
arr.push_back(t);
}
//이분탐색은 우선, 정렬 필수 !!
sort(arr.begin(), arr.end());
cin >> m ;
while(m--) {
cin >> t;
cout << upperBound(t, arr, n) - lowerBound(t, arr, n) << '\n';
}
return 0;
}
'기록 > 알고리즘 스터디 알튜비튜 5기✨' 카테고리의 다른 글
[ 알튜비튜 6기 ] 6개월 전엔 못풀고 끙끙대던 코드를.. 다시 풀어보다 ! (1) | 2024.03.07 |
---|---|
[ 11주차 투포인터🚩] 개념 + 활용 문제 ( 백준 c++ 11659 구간 합 구하기 4 / 21921 블로그 / 2470 두 용액 ) #누적합 #슬라이딩윈도우 (0) | 2023.11.10 |
[ 8주차 DFS & BFS ] 개념 정리 (0) | 2023.10.10 |
[ 우선순위 큐 ] 개념 + 필수 과제 ( 백준 14235 크리스마스 선물 c++) (0) | 2023.09.23 |
[ 우선순위 큐 ] 구현 과제 (백준 2607 비슷한 단어 c++) +멘토 코멘트 (0) | 2023.09.20 |