10815: 숫자 카드

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

10815번: 숫자 카드

설명

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

핵심 아이디어

• 카드의 수가 최대 500,000이기 때문에 비교시 이분 탐색으로 탐색 시간을 줄여야 한다. C++은 binary_search()를 제공한다. 이분탐색을 위해 모든 요소를 정렬시키는 것도 있지말자!

이진 탐색(Binary Search)

이진 탐색은 정렬된 상태에 있는 데이터에서 특정한 값을 찾아내는 알고리즘이다. 탐색 범위를 반으로 나눈 다음, target 값을 포함하는 범위를 좁혀나가는 방식으로 동작한다. 기본적으로 배열의 인덱스를 기준으로 배열 내의 값을 탐색하는데 사용되지만, 리스트, 트리 등에서도 사용 가능하다. 

• 반드시 정렬되어 있는 상태에서 사용 가능하다.
• 시간 복잡도는 O(logN)으로, 배열의 크기에 비례하여 실행 시간이 증가한다. 따라서 대용량 데이터에서 특정 값의 위치를 찾는데 용이하다. 

1. 정렬된 배열에서 중간 인덱스(mid)를 찾는다.
2. target 값과 중간 값을 비교한다.
3. target 값이 중간 값보다 작으면 mid를 기준으로 왼쪽 부분 배열을 탐색한다.
4. target 값이 중간 값보다 크면 mid를 기준으로 오른쪽 부분 배열을 탐색한다.
5. 탐색 범위를 반으로 줄인다.
6. 탐색 범위가 더 이상 없을 때까지 위 과정을 반복한다. 

따라서 이진 탐색은 탐색 범위를 반으로 좁혀가며 데이터를 찾는다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다. 즉, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다. 

코드 구현

c++

해당 코드는 C++ 에서 제공하는 binary_search() 기능 활용

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;


vector<int> arr;
// 결과를 담을 벡터 선언
vector<int> ans;
int main() {
	ios::sync_with_stdio(false);
	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;
	while (m--) {
		int target;
		cin >> target;
		// 시작, 끝, 타겟
		if (binary_search(arr.begin(), arr.end(), target)) {
			ans.push_back(1);
		}
		else {
			ans.push_back(0);
		}

	}

	// 여기서 m이 0이 된 상태이기 때문에 m을 넣으면 결과가 출력되지 않는다.
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}
	return 0;

}

 

해당 코드는 이진 탐색 기능을 직접 구현해서 풀은 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int n;
vector<int> arr;

int m;
vector<int> ans;

int binarySearch(vector<int>& arr, int start, int end, int target) {
	int mid;
	while (start <= end) {
		mid = (start + end) / 2;
		// 만약 중간값이 정답이라면
		if (arr[mid] == target) {
			return 1;
			
		}
		// 만약 타켓값이 중간값 보다 작다면 끝점을 옮긴다.
		else if (arr[mid] > target) end = mid - 1;
		// 만약 타갓값이 중간값 보다 크다면 시작점을 업데이트
		else if (arr[mid] < target) start = mid + 1;
	}
	// 이진 탐색후 찾고자 하는 값이 없다면
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	sort(arr.begin(), arr.end());
	cin >> m;
	while (m--) {
		int target;
		cin >> target;

		int result = binarySearch(arr, 0, n - 1, target);
		ans.push_back(result);
	}


	// 이진 탐색 후 m은 0
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}
}