[백준 1920번 C++] 수 찾기

대표적인 탐색 기본 문제이다.

기본적으로 투포인터나 이분 탐색 알고리즘을 통해 찾을 수 있지만, 본 문제는 이분탐색 알고리즘을 활용해 풀었다. 

참고로 이분 탐색과 투포인터 알고리즘의 차이점은 다음과 같다.

	이분 탐색(이진 탐색)	투포인터
시간복잡도	O(log N)	O(N)
방식	mid를 사용해 연산마다 탐색해야하는 데이터를 절반으로 줄임(log N)	양 끝단(혹은 첫 인덱스에서)시작하여 한칸씩 이동하며 적절한 값을 찾음
조건	데이터가 정렬된 상태에서 가능	상관 없음

투포인터 알고리즘의 경우 양끝단(혹은 첫 인덱스)에서 시작하여 한칸씩 이동하며 알맞은 값을  찾기 때문에 구간 합을 구할 때 유용하게 사용할 수 있다. 이분탐색 알고리즘은 특정한 값을 찾고자 할때 인덱스의 중간값을 사용하여 찾고자하는 값과 비교하여 해당 값보다 작거나 클때 mid를 조절하며 찾기 때문에 시간 복잡도를 크게 줄일 수 있다. 

brute-force 방식과 devide-conquer방식 알고리즘의 차이

상단 GIF에서 볼 수 있듯이, 이진탐색을 활용하면 총 3번의 STEP으로 원하는 값을 찾을 수 있다.

 

이분 탐색을 통한 문제 풀이

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

using namespace std;
vector<int> arr;

int BinarySearch(int num) {
	int start = 0;
	int end = arr.size() - 1;
	int mid = 0;
	
	while (start<=end) {
		mid = (start + end) / 2;
		if (num == arr[mid]) return 1;
		else if (num < arr[mid]) end = mid - 1;
		else start = mid + 1;
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int N, M;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	
	}

	sort(arr.begin(), arr.end());

	cin >> M;
	for (int i = 0; i < M; i++) {
		int tmp=0;
		cin >> tmp;
		cout << BinarySearch(tmp) << "\n";
	}
}

시간 초과 문제를 해결하기위해서 iosbase::sync_with_studio(0)와 cin.tie(0)는 꼭 코드로 추가하도록 한다.

(참고로 vector는 arr보다 push하는 연산속도가 더 빠르다고 한다) 

또한 if 문을 작성할 때 if, else if, else 순으로 작성하여 불필요한 조건을 일일이 확인하는 일이 없도록 한다(처음에 전부 if문으로 탐색했다가 시간초과남 ㅠ)