큰 차이 없습니다. 시간 초과가 날 정도라면 합병 정렬을 잘못 짜신 것이고, 어디가 잘못됐는지는 코드를 보아야 알 수 있습니다.
질문글에 맞는 코드는 크게 필요성이 없습니다. 틀린 코드를 먼저 올려주시는 것이 바람직합니다.
이 코드에서 시간을 유의미하게 단축시키는 제일 확실한 방법은 fread 등의 빠른 입출력을 사용하는 것인데, 그 외에는 크게 비효율적인 부분은 없어 보입니다.
1920번 - 수 찾기
해당 코드에는 크게 두 가지 문제점이 있습니다.
1. merge_sort 함수의 반환형이 int로 되어 있는데, 실제로는 아무것도 반환하지 않고 있습니다.
2. merge 함수에서 sizeof(int) * (e + 1)만큼을 매번 할당하는 것은 합병 정렬에서 매우 자주 보이는, 해서는 안 되는 실수입니다. 합병 정렬이 O(nlogn)이 보장되는 것은 merge 함수가 다루는 원소의 개수를 다 합쳤을 때 O(nlogn)이 되기 때문입니다. 그런데 메모리를 할당하는 것도 시간이 걸리는 일이고 그 범위 역시 시간 복잡도에 영향을 끼칩니다. merge 함수가 다루는 원소의 범위인 e-s+1이 아니라 e만큼씩을 할당을 하게 되면 전체 과정에서는 O(nlogn)이 아니라 O(n^2)에 해당하는 메모리 할당 / 해제가 일어나게 됩니다. e-s+1만큼의 메모리만을 할당해서 인덱스를 정확히 대응시키거나, 미리 할당된 고정된 배열에서 모든 작업을 수행하는 것 등이 방법입니다.
댓글을 작성하려면 로그인해야 합니다.
akqjqcjs7 3년 전
문제를 처음에는 합병 정렬 과 이분탐색을 이용해 문제를 풀었지만 시간초과가 나와 qsort를 이용해 풀었더니 통과했습니다.
올린 코드는 qsort를 이용해 푼 코드입니다.
1. 범위가 큰 경우에는 합병정렬보다 qsort보다 정렬시간이 빠른가요?
2. 코드에서 시간을 좀 더 단축 시킬 수 있다면 어떤 방법이 있을까요?