11004번 - K번째 수
quickselect 알고리즘을 구현하려고 한 코드입니다.
88% 근처에서 "메모리 초과"를 받습니다.
최악의 경우 사용하게 되는 배열의 총 길이를 생각하면 2n <= 10^7 인데 왜 메모리 초과가 뜨는지 잘 모르겠습니다.
파이썬 숫자형에 대해서 좀 더 알아보니 충분히 작은 범위에서의 int는 각각 28byte, 2^30 근처에서는 32byte를 사용한다고 합니다.
이것 때문에 메모리 초과가 나는 것인가요?
https://ahracho.github.io/posts/python/2017-05-09-python-integer-overflow/
최악의 경우는 quick_select가 smaller와 bigger를 1 : n-1로 나누고, bigger 쪽이 다시 1 : n-2로 나뉘고, 다시 n-2가 1 : n-3으로 나뉘고... 해서 1, 2, 3, ... n-1개로 나뉜 리스트들이 전부 존재하게 되는 O(n^2)입니다.
만들어왔습니다
댓글을 작성하려면 로그인해야 합니다.
chltjrwns1gh 4년 전
quickselect 알고리즘을 구현하려고 한 코드입니다.
88% 근처에서 "메모리 초과"를 받습니다.
최악의 경우 사용하게 되는 배열의 총 길이를 생각하면 2n <= 10^7 인데 왜 메모리 초과가 뜨는지 잘 모르겠습니다.
파이썬 숫자형에 대해서 좀 더 알아보니 충분히 작은 범위에서의 int는 각각 28byte, 2^30 근처에서는 32byte를 사용한다고 합니다.
이것 때문에 메모리 초과가 나는 것인가요?
https://ahracho.github.io/posts/python/2017-05-09-python-integer-overflow/