thfdldl   3년 전

머지소트를 보통 재귀호출로 짜는것으로 알고 있습니다.

잘 돌가는거 같은데 시간초가가 뜸니다..

시간초가 문제는 어떻게 해결해야하나요..ㅠㅠ 

이중 반복문을 쓴 것도 아닌데 어떻게 하면 더 시간을 줄일수 있을지 궁금합니다!!


toysmars   3년 전

merge()가 호출될때마다 배열을 새로 할당하는게 문제일까요?

chogahui05   3년 전

네. 배열의 최대 크기가 100만인데

merge가 호출이 될 때마다 새로 100만짜리 배열을 할당하면.. 음.. 일단 4byte짜리 변수 배열을 할당했다고 한다면..

100만 * 4byte = 4Mbyte네요.


가비지 콜렉터의 minor gc와 major gc를 구글링 해 보시는 거 추천드립니다.

gc 작업은 생각보다 무거운 작업입니다. gc 작업을 할 때는 오로지 gc만 수행해야 하는 것도 있고요.


알고리즘도 그렇게 간단치는 않습니다.

예를 들어, 운영체제나 프로그래밍 언어 시간에 배우는 mark & sweep 알고리즘의 경우에는


(1) 모든 객체를 조사합니다.

(2) unreachble한 것을 조사합니다. root로부터.

https://www.hboehm.info/gc/com...

chogahui05   3년 전

그냥 메인이나, 아니면 merge sort를 수행하게 하기 위한 함수를 따로 만들어서

거기에서 resultarr 배열을 만들고

merge 함수를 호출할 때 resultarr 배열을 (어짜피 주소값을 저장하니까 값복사로 넘겨도 상관 없겠죠..)

값복사 하는 식으로 넘기면 될 듯 싶네요. 알고리즘 자체는 맞습니다.

thfdldl   3년 전

정말 감사합니다. 통과됐네요 드디어ㅠㅠ!!

많이 배워갑니다!!

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