akqjqcjs7   3년 전

문제를 처음에는 합병 정렬 과 이분탐색을 이용해 문제를 풀었지만 시간초과가 나와 qsort를 이용해 풀었더니 통과했습니다.

올린 코드는 qsort를 이용해 푼 코드입니다.

1. 범위가 큰 경우에는 합병정렬보다 qsort보다 정렬시간이 빠른가요?

2. 코드에서 시간을 좀 더 단축 시킬 수 있다면 어떤 방법이 있을까요?

djm03178   3년 전

큰 차이 없습니다. 시간 초과가 날 정도라면 합병 정렬을 잘못 짜신 것이고, 어디가 잘못됐는지는 코드를 보아야 알 수 있습니다.

질문글에 맞는 코드는 크게 필요성이 없습니다. 틀린 코드를 먼저 올려주시는 것이 바람직합니다.

이 코드에서 시간을 유의미하게 단축시키는 제일 확실한 방법은 fread 등의 빠른 입출력을 사용하는 것인데, 그 외에는 크게 비효율적인 부분은 없어 보입니다.

guftkcldh   3년 전

맵이나 해쉬를 쓰면 빠르게 풀 수 있어요

akqjqcjs7   3년 전

합병 정렬코드 수정해서 다시 올렸습니다. 맵이나 해쉬는 아직 공부하지 못해서 이번 기회에 공부하겠습니다.

djm03178   3년 전

해당 코드에는 크게 두 가지 문제점이 있습니다.

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년 전

1. 코드에 전체적인 내용만 이해하고 사소한 부분을 놓쳤네요. 감사합니다.

2. 저는 merge함수가 호출될때 매번 공간을 할당받아야한다고 생각했습니다. 근데 그게 시간쪽에 영향을 끼친다고는 생각을 못했습니다.

정말로 감사합니다.

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