[백준] 1920 C언어

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

1920번: 수 찾기

단순하게 for문 2번 돌리면 되는 거 아닌가? 생각하고 오분만에 코드 작성해서 냈는데 시간 초과, outofbound가 떴다. 바로 구글링 해보니까 퀵정렬 + 이진탐색으로 푸는 것 같다. 종강하고 한 번도 보지 않은 자료구조 책을 펼쳐 보자.

 

C언어의 퀵 정렬 함수

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* arg1, const void* arg2) {
	if (*(double*)arg1 > *(double*)arg2) {
		return 1;
	}
	else if (*(double*)arg1 == *(double*)arg2) {
		return 0;
	}
	else
		return -1;
}

int main(void) {
	int i;
	double list[5] = { 2.1, 0.9, 1.6, 3.8, 1.2 };
	qsort((void*)list, (size_t)5, sizeof(double), compare);

	for (i = 0; i < 5; i++) {
		printf("%.1f ", list[i]);
	}
	return 0;
}

 

출처: C언어로 쉽게 풀어쓴 자료구조

 

qsort()의 원형은

void qsort(
	void *base, // 배열의 시작 주소
    size_t num, // 배열 요소의 개수
    size_t width, // 배열 요소 하자의 크기(바이트 단위)
    int(*compare)(const void *, const void *)
    // 포인터를 통하여 두 개 요소를 비교하여 비교 결과를 정수로 반환

)

즉 compare 함수를 따로 작성한 다음에 qsort({배열 시작 주소}, {배열 길이}, {배열 요소 하나의 크기}, compare 함수)라고 써 주면 된다. 한 번 써보니까 버블정렬이나 머지 정렬 구현하는 것보다 훨씬 편해서 잘 외우고 연습해서 앞으로 퀵소트만 많이 쓸 것 같다.

 

문제를 풀기 위해 퀵소트를 구현하면

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int compare(const void* arg1, const void* arg2) {
	if (*(int*)arg1 > *(int*)arg2) {
		return 1;
	}
	else if (*(double*)arg1 == *(double*)arg2) {
		return 0;
	}
	else
		return -1;
}


int m[100001] = { 0 };

int main(void) {

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

	for (int i = 0; i < n; i++) {
		printf("%d ", m[i]);
	}

	printf("\n");

	qsort((void*)m, (size_t)n, sizeof(int), compare);

	for (int i = 0; i < n; i++) {
		printf("%d ", m[i]);
	}


	return 0;
}

위와 같다. 이제 이진 탐색을 구현해보자.

 

이진 탐색이란?

- 정렬된 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지 알아내고, 탐색의 범위를 반으로 줄여가며 탐색을 진행

- 레코드의 집합을 두 부분으로 나누어서 탐색하고자 하는 키를 갖는 레코드가 어느 부분에 속하는가를 결정하여 그 부분에 대하여 순환적으로 탐색을 수행

- 분할 정복 탐색 기법

- 이진 트리를 탐색하는 방법 중 하나

- 평균 탐색 시간과 최악의 탐색 시간은 O(log⑵n)

- 레코드의 수가 많을수록 효과적(탐색할 레코드를 반씩 줄여가면서 탐색하므로)

- 탐색할 코드가 미리 정렬되어 있는 경우에만 사용할 수 있는 방법

 

그래서 코드를 끝까지 작성하면

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int m[100001] = { 0 };

int compare(const void* arg1, const void* arg2) {
	if (*(int*)arg1 > *(int*)arg2) {
		return 1;
	}
	else if (*(double*)arg1 == *(double*)arg2) {
		return 0;
	}
	else
		return -1;
}

int search_binary(int key, int low, int high) {
	int middle;
	while (low <= high) {
		middle = (low + high) / 2;
		if (key == m[middle]) {
			return 1;
		}
		else if (key < m[middle]) {
			return search_binary(key, low, middle - 1);
		}
		else {
			return search_binary(key, middle + 1, high);
		}
	}
	return 0;
}



int main(void) {

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

	/*
	for (int i = 0; i < n; i++) {
		printf("%d ", m[i]);
	}
	
	* printf("\n");
	* 	for (int i = 0; i < n; i++) {
		printf("%d ", m[i]);
	}
	*/
	

	qsort((void*)m, (size_t)n, sizeof(int), compare);

	int t;
	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		scanf("%d", &input);
		printf("%d\n", search_binary(input, 0, n));
	}


	return 0;
}

이렇게 된다!

 

맞았다!!!

 

배운 것

1. 퀵 소트

2. 이진 탐색

3. 변수 재활용하지 말자. main에서 처음 선언한 n에 값 입력할 때 정수, 탐색할 값 개수 정수 각각 넣었다가 어디서 틀렸는지 한참 헤맸다.