[바킹독의 실전 알고리즘] 0x13강 - 이분탐색

1. 알고리즘 설명

 

이분탐색이란?

정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가면 찾는 탐색 방법

 

ex)

정수 10개로 이뤄진 정렬된 배열에서 선형 탐색의 경우 탐색 시 앞에서부터 순차적으로 탐색을 하게 됨. 그렇게 한다면 시간복잡도는 O(N). 하지만 이분탐색의 경우 배열을 반절로 나눠가면서 효율적으로 탐색하여 시간복잡도를 O(log N)으로 줄일 수 있음!

 

이분탐색의 과정 예시 - 반절로 계속 줄여나가면서 탐색 중!

 

2. 구현 및 STL

 

📌 이분탐색 문제 유형의 경우 간단한 문제들은 STL에 존재하는 함수들을 이용해 구현할 게 별로 없지만, 살짝만 복잡해져도 난이도가 훨씬 올라가게 됨. 따라서 코테 공부 초보 단계일 경우 개념과 STL 사용법을 위주로 공부하고 다른 주요 강의들에 집중하는 것을 추천.

 

🎯 BOJ 1920번: 수 찾기 문제

 

1) 이분탐색 직접 구현

// http://boj.kr/e8e4c3e6a0f94f43bc21a192492c34a8
#include <bits/stdc++.h>
using namespace std;

int a[100005];
int n;

int binarysearch(int target){ //target을 찾기 위해 탐색하는 함수
  int st = 0; 
  int en = n-1;
  while(st <= en){ 
    int mid = (st+en)/2; //C++ 특성 상 홀수/2를 하면 나머지는 버리게 됨. ex) (0+9)/2=4
    if(a[mid] < target) 
      st = mid+1;
    else if(a[mid] > target)
      en = mid-1;
    else
      return 1;
  }
  return 0; // st > en일 경우 while문을 탈출
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) 
  	cin >> a[i];
  sort(a, a+n);
  int m;
  cin >> m;
  while(m--){
    int t;
    cin >> t;
    cout << binarysearch(t) << '\n';
  }
}

 

2) binary_search 함수로 구현

STL에는 binary_search 함수가 있어 범위를 주면 주어진 범위 내에 원소가 있는지 여부를 O(log N)에 불리언 값 (true/false)로 알려줌. 이때, 범위는 반드시 오름차순으로 정렬이 되어 있어야 하면 그렇지 않을 경우 값이 들어있는데 들어있지 않다고 판단하는 일 발생 가능.. (있는데 없었습니다..)

 

// http://boj.kr/0d0917e336ac4d709029df43a9127ace
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a,a+n); //오름차순으로 배열 정렬
  int m;
  cin >> m;
  while(m--){
    int t;
    cin >> t;
    cout << binary_search(a, a+n, t) << '\n'; //a부터(즉, 시작부터) a+n(배열 끝)까지 t가 있는지 확인
    //vector를 사용한다면 a.begin()이나 a.end()를 넣어주면 됨
  }
}

 

🎯 BOJ 10816번: 숫자 카드 2 문제

 

 

1) 직접 구현 하는 방법

// http://boj.kr/e78b47fa3e08436faada666bafcf9501
#include <bits/stdc++.h>
using namespace std;

int a[500005];
int n;

int lower_idx(int target, int len){
  int st = 0;
  int en = len;
  while(st < en){
    int mid = (st+en)/2;
    if(a[mid] >= target) en = mid;
    else st = mid+1;
  }
  return st;
}

int upper_idx(int target, int len){
  int st = 0;
  int en = len;
  while(st < en){
    int mid = (st+en)/2;
    if(a[mid] > target) en = mid;
    else st = mid+1;
  }
  return st;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  sort(a,a+n);
  int m;
  cin >> m;
  while(m--){
    int t;
    cin >> t;
    cout << upper_idx(t,n)-lower_idx(t,n) << '\n';
  }
}

 

2) lower_bound, upper_bound 활용하는 방법 in STL

 

lower_bound와 upper_bound 함수의 경우 target이 들어갈 수 있는 가장 왼쪽 위치와 오른쪽 위치를 반환하는 함수임.

반환 자료형은 배열을 사용할 경우 포인터, vector일 경우 iterator가 됨. 더불어 equal_range라고 하여 lower_bound와 upper_bound의 결과를 pair로 반환해주는 함수도 존재함!

 

📚 두 함수에 대한 자세한 설명은 이 블로그를 참고하면 좋을 듯 👍

 

cf) iterator(반복자)

볼 때마다 뭔지 느낌은 알겠는데 정확하게는 모르겠는 iterator! 🙄iterator(반복자)란 STL 컨테이너에 저장된 요소를 반복적으로 순회하여 각각의 요소에 대한 접근을 제공하는 객체임. 즉, 반복자는 포인터의 일종이며 일반화한 개념이라고 생각하면 될듯. (참고:여기)

 

🧨 이분 탐색 주의사항 

1) 이분탐색을 하고자 한다면 주어진 배열은 정렬되어 있어야 함

정렬되어있지 않은 배열에서 binary_search, lower_bound, upper_bound 등을 사용하게 된다면 이상한 결과가 나옴. 있는데 없다고 판단하는 경우! (위에서 말한 경우임)

 

2) 무한 루프에 빠지지 않게 mid 값을 정해야 함

정렬 단원에서는 STL sort 함수를 쓰면 장땡이다!라는 것과 다르게 이분탐색 문제에서는 그렇지 못함. STL에 많은 편리한 함수들이 구현이 되어 있지만, STL이 도움이 안되는 경우(ex. Parametric search) 직접 이분 탐색을 구현해야 하는 경우가 많음. 이 때 mid 값을 설정을 잘 해줘야 하는 게, 잘못하면 무한 루프에 빠질 수도 있다! 보통 st와 en이 1 차이가 나는 상황에서 mid를 고려해보면, mid를 처음에 정의를 할 때 어떤 식으로 정의해야하는지 잘 파악할 수 있을 것임. 

 

예를 들어, 정렬된 배열에서 target 값보다 값이 작은 원소 중 가장 오른쪽에 있는 원소를 찾는다고 가정하자. 

이런 식으로 구현할 수 있다. 이때 mid = (st+en)/2

하지만 이때 만약 func(16, 10) 호출 시 st=2 / en=3인 상황이 생겨 mid=2가 된다면 이후 조건들에 따라 st=2 & en=3인 상황이 무한 루프에 빠지게 됨. 이런 일을 막기 위해서 mid = (st+en+1)/2로 계산을 해주면 됨!