글 읽기 - 재귀함수로 짜면 시간초과가 나나요?

p_ce1052 4년 전 0

왜 시간초과가 날까요? 재귀함수로 짠게 문제일까요? 알고리즘은 잘 동작하는것 같습니다.

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

int array[1000001];
char check[100000];

int compare (const void *first,const void *second)
{
    if (*(int*)first > *(int*)second)
        return 1;
    else if (*(int*)first < *(int*)second)
        return -1;
    else 
        return 0;
}

int binarysearch(int data,int start,int end){
	int btn;
	int middle=(end+start)/2;
	if(start==end) return data==array[middle]?1:0;
	if(data>array[middle]){
		return binarysearch(data,start+1,end);
	}
	else if(data<array[middle]){
		return binarysearch(data,start,end-1);
	}
	else if(data==array[middle]) return 1;
}
int main(){
	int i,j;
	int n,m;
	int num;
	scanf("%d",&n);
	for(i=0; i<n; i++){
		scanf("%d",array+i);
	}
	qsort(array,n,sizeof(int),compare);
	
	scanf("%d",&m);
	for(j=0; j<m; j++){
		scanf("%d",&num);
		check[j]=binarysearch(num,0,n-1);
	}
	for(j=0; j<m; j++){
		printf("%d\n",check[j]);
	}
	return 0;
}

djm03178 4년 전 0

"알고리즘은 잘 동작하는것 같습니다."

이 말은 어떻게 보면 맞고, 어떻게 보면 틀립니다.

1. '알고리즘'이 '그냥 답은 나온다'는 뜻인 경우: 맞습니다. 하지만 시간이 오래 걸리는 것과는 무관합니다.

2. '알고리즘'이 '투 포인터'인 경우: 맞습니다. 하지만 그렇기 때문에 O(nm)이라 당연히 시간 초과가 됩니다.

3. '알고리즘'이 '이분 탐색'인 경우: 틀립니다. 이분 탐색이 되려면 middle에서 찾는 걸 실패했을 때 [start, middle) 또는 (middle, end]로 가야 하는데 이 코드는 [start, end-1] 또는 [start+1, end]로 가고 있기 때문입니다.

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

문제

문제

출처

ICPC

재귀함수로 짜면 시간초과가 나나요?

p_ce1052 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말