글 읽기 - 선택정렬과 이진탐색..

tjdgns9246 7년 전 0

다음과 같이 첫번째 배열은 정렬을 해준 뒤 이진탐색으로 검색을 했습니다.

그런데 시간초과가 뜨네요... 어떻게 해야 할 지 모르겠습니다.

도움 좀 주실 분 계신가요?

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

void swap(int* a, int* b);
void selectionSort(int* list, int n);
int binarySearch(int* list, int n, int searchNum);

int main()
{
    int i, j, n, m, min, *list_n, *list_m;
    
    // scanning for n
    scanf("%d", &n);
    list_n = (int *)malloc(sizeof(int) * n);
    for(i = 0; i < n; i++)
    	scanf("%d", &list_n[i]);
    // sorting for list_n
    selectionSort(list_n, n);
    
    // scanning for m
    scanf("%d", &m);
    list_m = (int *)malloc(sizeof(int) * m);
    for(i = 0; i < m; i++)
        scanf("%d", &list_m[i]);
    
    for(i = 0; i < m; i++)
    {
    	if(binarySearch(list_n, n, list_m[i]) != -1)
    		printf("1\n");
    	else
    		printf("0\n");
    	
    }
}

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void selectionSort(int* list, int n)
{
	int i, j, min;
	
	for(i = 0; i < n; i++)
	{
		min = i;
		
		for(j = i + 1; j < n; j++)
		{
			if(list[j] < list[min])
				min = j;
		}
		
		swap(&list[min], &list[i]);
	}
}

int binarySearch(int* list, int n, int searchNum)
{
	int left = 0;
	int right = n;
	int mid;
	
	while(left < right)
	{
		mid = (left + right) / 2;
		if(searchNum < list[mid])		right = mid - 1;
		else if(searchNum == list[mid])	return list[mid];
		else if(searchNum > list[mid])	left = mid + 1;
	}
	
	return -1;
}

tjdgns9246 7년 전 0

@indioindio님, 코드를 실행했을 때 걸리는 시간을 제한시간이랑 비교를 어떻게 하나요?

시간복잡도라는 걸 잠깐 공부했긴 했었는데... 정확한 개념을 이해하지 못하겠더라구요.

어떤 기준으로 느리다고 생각하신건가요?

@opencv님, STL에서 제공하는 sort함수는 어떤건가요?

indioindio 7년 전 0

글쎄요 경험적으로 본다면 작성하신 selectionSort를 gcc -O2 로 컴파일한 다음 임의로 생성한 100000개의 입력에 대해 실행하였을 때 6.3초 정도 걸립니다. (최적화 옵션을 끄면 22초 정도 걸리네요)

시간복잡도 측면에서 볼 때, 선택정렬은 O(n^2)입니다. 정확한 설명은 절대 아니지만, 대충 입력의 크기에 따라 걸리는 시간의 증가양상이 n^2의 그래프와 흡사하다 정도로 이해하시면 될 것 같습니다. 모 책에서는 시간복잡도에 입력의 크기를 대입해서 얻은 값에 대해서, 1억 당 1초가 걸린다고 생각하면 된다고 합니다. 10만^2는 100억이니 이 방법으로 계산하면 100초가 걸립니다. (차이가 좀 있지만... 근사값이기도 하고, 선택정렬은 상수요소가 적기도 하고, 제한시간은 초과한다 정도로 이해하시면 될 것 같습니다.)

stl 의 sort는 구현체에 따라 다르겠지만 보통 퀵소트+힙소트로 구현되어 있는 것 같네요. 퀵정렬이나 힙정렬은 O(NlogN)의 복잡도를 갖는데요, 위의 계산법에 따르면 1660964의 값을 가지니 1초 내에 들어오리라고 예상할 수 있겠죠.

indioindio 7년 전 0

돌려보니 약 0.05초정도 걸리네요

tjdgns9246 7년 전 0

@indioindio 님, 덕분에 좋은 정보 알아갑니다 ^^ 감사합니다.

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

문제

문제

출처

ICPC

선택정렬과 이진탐색..

tjdgns9246 7년 전 0

indioindio 7년 전 0

opencv 7년 전 0

tjdgns9246 7년 전 0

indioindio 7년 전 0

indioindio 7년 전 0

tjdgns9246 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말