unta   2년 전

* 각 코드가 너무 긴 관계로 별도의 링크로 첨부합니다.

병합 과정에서 계속 할당: http://boj.kr/ee53a99fc1104730b2dd00b2949ae03d
재귀 전 한 번만 할당: http://boj.kr/9d50735175054dbe8eaeaae36384b71a


이 문제를 풀기 위해 머지 소트를 STL의 qsort와 유사하게 구현해보았습니다.

처음에는 머지 소트에서 할당되는 sorted 임시 배열이 사용하는 리소스를 줄이고자 각각의 병합 함수에서 따로 할당하는 방식으로 구현해보았습니다.

그런데 문득 이런 걸로 얼마나 메모리를 절약하는지가 궁금해서 머지 소트의 병합 이전에 미리 sorted를 생성하여 구현해보았더니 오히려 메모리 사용량이 줄어듦을 확인했습니다.


이론상으론 동적할당의 횟수는 줄겠지만, 각각의 메모리가 할당되는 크기가 줄어들어 시간을 늘고 메모리는 줄 것이라 예상했습니다.

그러나 시간은 오차 범위 내이고 메모리는 오히려 줄었더군요, 이런 결과가 나온 이유가 궁금합니다.


+ C/CPP의 STL에서 제공하는 qsrot 및 std::sort 등의 함수는 언스테이블 정렬로 알고 있는데 stdlib.h의 qsort를 이용한 풀이가 정답처리가 되었습니다.

로컬 환경에서 qsrot가 언스테이블함을 확인하였는데 백준에서 정답처리된 이유가 궁금합니다.

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