백준 시간 초과와 시간 복잡도

*발 안녕

 

너희는 백준 2477번 참외밭 문제를 풀어보았니?

문제에서 젖비린내 난다고?

*발 샤워부터 하고 와 파오후 *들아ㅋㅋ

 

거두절미(去頭截尾)하고 시간 초과가 났던 이 문제를 다시 생각해 보면서

시간 복잡도와 수행 시간에 대해 알아보자고

---

cpu가 1초안에 수행할 수 있는 연산은 1억번이라고 생각하는것이 국룰이란다

그러면 상당히 간단해 지는데,

 

시간제한이 1초라면 (N은 입력) 대략

O(1), O(log N)	N    <=    ∞
O(N)	N    <=    100,000,000(1억)
O(N log N)	N    <=    13,993,959(1천 3백만)
O(N²)	N    <=    10,000(1만)
O(N³)	N    <=    464
O(2ᴺ)	N    <=    26
O(N!)	N    <=    12

이정도로 어림잡을 수 있다.

 

물론 빅 오 노테이션(Big-O notation)을 기준으로 했기때문에 

무시되는 상수나 마이너 항들을 고려한다면 결과가 또 천차 만별이 될것이니 참고 하도록 해

 

 

 

 

*나게 유용하군

 

 

 

 

 

---

자, 이제 문제로 돌아가 보자고

이 문제에서 입력받을 수 있는 최대 자료 개수는

1,000,000개 라는 것을 알 수 있지 

 

처음 순수했던 나는 이분탐색은 커녕 정렬도 안하고 선형탐색으로 풀려고 했지 (저능아는 아니고 3달만에 풀어서 그럼)

이 코드는 너무 역해서 보여주진 못하고 대충 계산만 해본다면

 

O(N²) 이니까 250,000,000,000 번의 연산 = 25초가 걸린다

 

오랫만에 시간초과를 보니까 아찔하더라 

그래서 정신 차리고 수정을 해봤어.

정렬을 하고 이진탐색을 하는 방식으로 말이지

 

하지만 멍청하게도 나는 정렬을 선택정렬로 해버렸고 똑같이 250,000,000,000의 연산을 하게 된 백준의 컴퓨터는

이렇게 큰 연산은 안들어 간다며 처참히 부서지고 말았지

 

두번의 같은 실수를 저지르고 나는 나에게 큰 실망을 해버렸지

그래서 그 다음은 바로 합병정령 빡구현을 박아버렸지

 

이게 마지막 코드야

#include <stdio.h>

int binary_search(int *arr, int start, int end, int target)
{
    if (start < end)
    {
	   int middle = start + (end - start) / 2;
	   if (arr[middle] == target)
		  return 1;
	   else if (target < arr[middle])
		  return binary_search(arr, start, middle, target);
	   else
		  return binary_search(arr, middle + 1, end, target);
    }
    else if (arr[start] == target)
	   return 1;
    return 0;
}

int* merge(int* arr, int start, int middle, int end){
    int i = start, j = middle+1, k = 0;
    int sorted[end-start+1];
    while(i <= middle && j <= end)
    {
        if(arr[i] <= arr[j])
	   {
            sorted[k] = arr[i];
            i++;
        }
        else{
            sorted[k] = arr[j];
            j++;
        }
        k++;
    }
    if(i > middle)
    {
        while(j <= end)
	   {
            sorted[k] = arr[j];
            k++;j++;
        }
    }
    else{
        while(i <= middle)
	   {
            sorted[k] = arr[i];
            k++;i++;
        }
    }
    for(int l=start; l<=end; l++)
    {
        arr[l] = sorted[l-start];
    }
    return arr;
}

int* merge_sort(int* arr, int start, int end)
{
    if(start < end)
    {
        int middle = (start + end) / 2;
        merge_sort(arr, start, middle);
        merge_sort(arr, middle+1, end);
        merge(arr, start, middle, end);
    }
    return arr;
}

int main()
{
    int n, m;
    scanf("%d", &n);
    int a[n];
    for(int i=0; i < n; i++)
    {
	   scanf("%d", &a[i]);
    }
    merge_sort(a, 0, n);
    scanf("%d", &m);
    int b[m];
    for(int i=0; i < m; i++)
    {
	   scanf("%d", &b[i]);
	   printf("%d ", binary_search(a, 0, n, b[i]));
    }
}

사용된 알고리즘인 합병정렬과 이분탐색은 각각

합병정렬	O(N log N)	6000000
이분탐색	O(log N)	6

(대략)번의 연산을 한다.

 

그렇기 때문에 빅 오 표기법 기준으로 6000006번의 연산이 이루어 지고 이는 이론적으로 0.6초의 수행시간을 가져간다



 

어때 이해가 잘 됐니??

이제 시간 초과가 뜨면 노트북 덮고 롤하러 가지 말고

시간복잡도를 생각하면서 다시 설계를 해보도록 하렴

이제 부모님께 효도 해야지

 

 

 

사랑해요:)