글 읽기 - 1920번 수찾기에 대한 질문

hayman42 5년 전 0

입문자라 질문 검색하면서 어떻게 아래 코드까지 왔는데 이해가 안되는 부분이 많아 도움 부탁드립니다. ㅠㅠ

첫번째로 아래와 같이 main 함수 밖에서 배열을 선언하면 메모리 초과가 안되는데 동적 할당을 하면 메모리 초과가 뜹니다. 오히려 동적 할당을 했을 때 메모리를 효율적으로 사용하는 것이라 생각했는데 왜 함수 밖 전역 변수로 선언해야 메모리 초과가 뜨지 않나요?

두번째로 아래 코드를 제출하면 시간 초과가 뜨는데... 어떤 문제가 있을까요? 정렬에는 qsort, 탐색엔 이진 탐색이 가장 효율적인 방법이라 알고 있었는데.. 아니면 제가 짠 함수에 잘못된 점이 있나요?

감사합니다.

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

int num[100000];
int given[100000];

int comparenum(const void *a, const void *b);
int binsearch(int *arr, int first, int last, int num);

int main(void)
{
	int n, i;
	scanf("%d", &n);

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

	qsort(num, n, sizeof(int), comparenum);

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

	for (i = 0;i < m;i++)
		scanf("%d", &given[i]);

	for (i = 0;i < m;i++)
		printf("%d\n", binsearch(num, 0, n - 1, given[i]));

	return 0;
}

int comparenum(const void *a, const void *b)
{
	if (*(int *)a > *(int *)b)
		return 1;
	else if (*(int *)a < *(int *)b)
		return -1;
	else
		return 0;
}

int binsearch(int *arr, int first, int last, int num)
{
	int f = first;
	int l = last;
	int mid;

	while (f != l)
	{
		mid = (f + l) / 2;

		if (num == arr[mid])
			return 1;
		else if (num > arr[mid])
			f = mid + 1;
		else
			l = mid - 1;
	}

	if (num == arr[f])
		return 1;
	else
		return 0;
}

djm03178 5년 전 1

첫째로, 메모리 초과가 뜬 제출 기록을 보니 n을 입력받은 뒤에 n개의 수를 입력받지 않고 num[i] = i*i; 라는 알 수 없는 식으로 채우셨더군요. 그러니 2번째 줄에 첫 수로 입력이 아주 큰 수가 들어오면 그 수가 m에 저장되고 그 크기만큼 메모리를 할당받으려 하니 메모리 초과가 난 것이고요.

둘째로 이 코드가 시간 초과가 나는 이유는 48번째 줄의 while문을 반드시 탈출한다는 보장이 없기 때문입니다. 다음의 케이스를 넣어보시고 원인을 분석해보세요.

1 2

hayman42 5년 전 0

첫번째는 다른 경우의 수 검사하려다 넣은걸 수정하지 않을걸 뒤늦게 알아버렸네요 동적할당 문제가 아니라 ㅠㅠ

두번째의 경우도 덕분에 깨달았습니다. f != l 에서 문제가 생겼었네요.

감사합니다~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1920번 수찾기에 대한 질문

hayman42 5년 전 0

djm03178 5년 전 1

hayman42 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말