[C] 백준 | 1920번 코드 - 수 찾기

>문제

> 핵심

이진탐색 알고리즘!

>풀이과정

어떻게 풀까 고민하다가.. 문제에서 정수의 범위를 -2^31 ~ 2^31 로 정해놓은 걸 보고

[+] 정수를 보관하는 배열이랑 [-] 정수를 보관하는 배열 두개를 만들어서 따로 저장한 다음,

반복문을 돌리면서 값을 찾으면 시간이 절반만 걸리지 않을까 싶어서 구현해봤는데 다행히 맞았다고 떴다.

 

근데 이런식으로 짜면 아무래도 낭비되는 공간이 많아서 좋은 알고리즘이라고 하기는 어려울 것 같다.

 

그래서 예전에 배웠던 이진탐색트리를 구현해 탐색하는 코드를 짜기로 했다.

 

예전에 수업시간때 배웠던 코드를 다 기록으로 남겨놨더니 복습하는데 정말 큰 도움이 된다.

그래서 이 블로그를 쓰는거기도 하고.. 기록을 남겨놓으면 언젠가는 도움이 되겠지.

 

 

걸리는 시간이 획기적으로 줄어들었다

 

이진탐색트리의 성능은, 최선의 경우 O(logn), 최악의 경우는 O(n)이라고 한다.

이중반복문 돌면서 찾으면 O(n^2)인데 이만하면 매우 효율적이다.

 

이거 말고도 AVL트리, 스플레이 트리,, 알고리즘 시간때 나를 고생시켰던 트리들이 있는데 그건 차마 손대기가 두렵다.

생각만 해도 머리가 아프다. 나중에 해야지..

 

----

그리고 다른사람이 짜놓은 코드를 보면서 배열을 이용한 이진탐색을 하는 방법을 배웠다.

배열을 통한 이진탐색은, 우선 배열이 정렬이 되어있어야 한다.

 

1. mid = (left + right) / 2

2. mid 값이 내가 찾고자 하는 값보다 큰지? 작은지? 같은지? 판단

3. 탐색 배열을 반으로 줄인 뒤 1번부터 반복. -> (left < right) 일때까지

 

크게 어려운 알고리즘은 아니다.

 

>깨달은점

이진탐색 알고리즘을 활용하면 탐색시간을 상당히 절약할 수 있다.

>코드

1. 처음에 짠 +-배열 분리

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
	int m, n, tmp, i, j, cnt = 0, m_cnt = 0;
	int table[100001];
	int m_table[100001];

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf(" %d", &tmp);

		if (tmp < 0)
			m_table[m_cnt++] = tmp;
		else
			table[cnt++] = tmp;
	}

	scanf(" %d", &m);

	for (i = 0; i < m; i++)
	{
		scanf(" %d", &tmp);

		if (tmp < 0)
		{
			for (j = 0; j < m_cnt; j++)
			{
				if (m_table[j] == tmp)
					break;
			}
			if (j == m_cnt)
				printf("0\n");
			else
				printf("1\n");
		}
		else
		{
			for (j = 0; j < cnt; j++)
			{
				if (table[j] == tmp)
					break;
			}
			if (j == cnt)
				printf("0\n");
			else
				printf("1\n");
		}
	}

	return 0;
}

 

2. 이진탐색트리 활용

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
	int data;
	struct TreeNode* left, * right;
}TreeNode;

TreeNode* insertNode(TreeNode* node, int data)
{
	if (node == NULL)
	{
		TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
		tmp->data = data;
		tmp->left = tmp->right = NULL;
		return tmp;
	}

	if (data < node->data)
		node->left = insertNode(node->left, data);
	else
		node->right = insertNode(node->right, data);

	return node;
}

TreeNode* Search(TreeNode* node, int data)
{
	if (node == NULL) return NULL;
	
	if (node->data == data) 
		return node;
	else if (node->data > data) 
		return Search(node->left, data);
	else 
		return Search(node->right, data);
}

int main()
{
	TreeNode* Root = NULL, *tmp = NULL;
	int i, n, m, data;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		scanf(" %d", &data);
		Root = insertNode(Root, data);
	}

	scanf(" %d", &m);

	for (i = 0; i < m; i++)
	{
		scanf(" %d", &data);
		tmp = Search(Root, data);

		if (tmp == NULL)
			printf("0\n");
		else
			printf("1\n");
	}

	return 0;
}

 

3. 이진탐색 (배열을 활용)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int compare(const void* first, const void* second)
{
	int* a = (int*)first;
	int* b = (int*)second;

	if (*a < *b)
		return -1;
	else
		return 1;
	return 0;
}

int binary_search(int list[], int n, int key)
{
	int left, mid, right;
	left = 0, right = n - 1;

	while (left <= right)
	{
		mid = (left + right) / 2;
		if (list[mid] == key)
			return 0;
		else if (list[mid] < key)
			left = mid + 1;
		else
			right = mid - 1;
	}
	
	return 1;
}

int main()
{
	int n, m, i, data;
	int* list;

	scanf("%d", &n);

	list = (int*)malloc(n * sizeof(int));

	for (i = 0; i < n; i++)
	{
		scanf(" %d", &list[i]);
	}

	qsort(list, n, sizeof(list[0]), compare);

	scanf(" %d", &m);

	for (i = 0; i < m; i++)
	{
		scanf(" %d", &data);
		
		if (binary_search(list, n, data) == 0)
			printf("1\n");
		else
			printf("0\n");
	}

	return 0;
}