[ 이분탐색🚩] 개념 + 활용 문제 ( 백준 c++ 1920 수 찾기 / 10816 숫자 카드 2 ) #UpperBound #LowerBound

2023. 11. 3 일자 이화여대 알고리즘 튜터링 프로그램, 알튜비튜의 수업 내용 정리본입니다.

 

🔍이분 탐색 ( BinarySearch )이란 ?

업다운 게임을 생각하면 된다 !

중간값과 찾아야하는 값을 비교해가며,

배열의 크기를 절반으로 줄이며 답을 찾는 알고리즘으로

반복문으로 구현하며, 시간 복잡도는 O(logN)

 

알고리즘 사용 전, 반드시 배열을 정렬해야 한다 !!

 

+) 이분 탐색의 대상 원소들을 트리에 넣으면 바이너리서치트리(binary search tree) !

BST를 중위 순회 (inorder) 하면 정렬된 순서의 배열이 나온다.

 

이분 탐색의 과정

 

이미지 출처 : https://velog.io/@reyang/C-%EC%84%A0%ED%98%95-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EA%B5%AC%ED%98%84

 

 

배열의 원소가 정렬된 상태라면, 특정 원소를 찾는 여러 방법들 중 이분 탐색이 가장 빠르다 !!

 

이분탐색은 분할 정복과 달리 답이 없는 문제부(절반)은 아예 버림 !

 

 

 

 

📌  코딩 테스트 관련 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는 타겟값이 처음 초과된 위치를 찾는 알고리즘이다.

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;
}