[백준] 1920번 수 찾기 (C++) - binary search

문제

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

코드

첫번째 시도

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n, m, a;
  vector<int> v;
  bool flag;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> a;
    v.push_back(a);    
  }

  cin >> m;
  for(int i=0; i<m; i++){
    flag = false;
    cin >> a;
    for(int j=0; j <n; j++){
      if(v[j] == a){
        flag = true;
        break;
      }
    }
    if(flag){
      cout << 1 <<'\n';
    } else{
      cout << 0 << '\n';
    }
  }
  
  return 0;
}

→ 시간초과 

 

binary search 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m, a;
  vector<int> v;
  bool flag;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> a;
    v.push_back(a);    
  }
  sort(v.begin(), v.end());

  cin >> m;

  for(int i=0; i<m; i++){
    flag = false;
    int start = 0;
    int end = n-1;
    int mid;
    cin >> a;
    while(end-start >= 0){
      mid = (start+end)/2;
      if(v[mid] == a){
        flag = true;
        break;
      }
      else if(v[mid] < a){
        start = mid+1;
      }
      else{
        end = mid-1;
      }
    }

    if(flag){
      cout << 1 <<'\n';
    } else{
      cout << 0 << '\n';
    }
  }

  return 0;
}

 

binary search 함수로 구현한 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int binary_search(vector<int>& v, int start, int end, int target){
  while(end-start >= 0){
    int mid = (start+end)/2;
    if(v[mid] == target){
      return 1;
    } 
    else if(v[mid] < target){
      start = mid + 1;
    }
    else{
      end = mid - 1;
    }
  }
  return 0;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, m, a;
  vector<int> v;

  cin >> n;
  for(int i=0; i<n; i++){
    cin >> a;
    v.push_back(a);    
  }
  sort(v.begin(), v.end());

  cin >> m;

  for(int i=0; i<m; i++){
    cin >> a;
    int result = binary_search(v, 0, n-1, a);
    cout << result << '\n';
  }

  return 0;
}

정리

처음에는 단순하게 for문을 돌려 처음부터 끝까지 확인하는 코드를 구현하였으나 시간 초과로 통과하지 못했다. 이 문제는 binary search로 문제를 해결할 수 있다.

 

binary search

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 

정렬된 리스트에만 사용할 수 있다.검색이 반복될 때마다 목표값을 찾을 확률이 두배가 되므로 속도가 빠르다. → O(logN)의 시간복잡도를 갖는다.

 

참조

https://jaimemin.tistory.com/587

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://tooo1.tistory.com/122