[백준(BOJ)]10815 - 숫자카드 (C/C++)

백준 10815번 이진탐색 문제. 단계 집합과 맵에 위치해 있다.

탐색의 범위를 잘못 생각하여 2번이나 틀려버렸다..

오늘은 이진탐색(Binary  Search)문제를 해결하였다. 문제만 본다면 그냥 탐색으로 풀 수도 있겠지만, 그렇게 풀면 시간 초과가 나올 것이 분명했기에 이진 탐색으로 문제를 해결하였다.

사실 오늘 하루종일 피곤했는데, 그래도 빠르게 문제를 해결했다ㅎ ㅎ 예전 대학교 알고리즘 수업 때에는 엄청 고생했던 것 같은데 다시 풀어보니 그때의 기억이 조금 살아난게 아닐까 싶었다.

 

이진 탐색은 배열의 탐색법중 하나로, 오름차순 정렬되어있는 배열에 내가 찾고자 하는 값을 얻는 방법이다.

탐색하는 방법으로는, 찾는 수를 배열의 중간값와 비교하여 재귀적으로 다시 함수를 호출해 범위를 좁혀나가고 값이 있는지 확인하는 방법으로, 시간 복잡도가 O(logN)으로 굉장히 빠른 알고리즘이다.

 

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

vector<int> card;
vector<int> inputNum;
bool binary_search(int start, int end, int Num);

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

	int N;
	cin >> N;

	for (int i = 0; i < N; ++i)
	{
		int k;
		cin >> k;
		card.push_back(k);
	}

	int M;
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int k;
		cin >> k;
		inputNum.push_back(k);
	}
	sort(card.begin(), card.end());

	for (int i = 0; i < M; ++i)
	{
		if (binary_search(0,N-1, inputNum[i]))
			cout << 1 << " ";
		else cout << 0 << " ";
	}
}

bool binary_search(int start, int end, int Num)
{
	bool t;
	int middle;
	middle = (start + end) / 2;
	
	if (Num == card[middle]) return true;
	if (start + 1 == end)
	{
		if (Num == card[start]) return true;
		else if (Num == card[end]) return true;
		return false;
	}
	if (Num > card[middle])
	{
		t = binary_search(middle, end, Num);
	}
	else
	{
		t = binary_search(start, middle, Num);
	}

	return t;
}

여기서 집중적으로 봐야 할 포인트는 binary_search함수로, middle값을 비교하여 찾고자 하는 Num값이 더 큰지 작은지에 따라 재귀적으로 함수를 호출해 준다는 점이다.

Num값이 더 작다면 end를, 더 크다면 start를 middle로 바꿔주어 재귀적으로 함수를 호출하고, 값을 찾기 때문에 각 호출마다 찾는 범위가 1/2로 줄어들기 때문에 시간복잡도가 짧게 나오는 것이다.

또한, 위 탐색법은 정렬되어 있어야 사용할 수 있기 때문에 vector자체를 sort 시켜주었다.

 

웃긴 점은, 옛날에 풀었던 문제가 재채점되어 틀렸음으로 바뀌어 다시 110번째 문제를 해결했다는 점이다ㅋㅋ

아마 다음 문제는 한번 더 탐색법을 풀거나, 정렬법에 관련된 문제를 풀 생각이다