파이썬의 속도, 메모리 사용량

요즘

수학 문제 푸는 느낌이라 재미없다고 안하던 백준을 하고 있다.

(코테 보다가 내 실력에 충격먹어서 그런건 아님. 절대 아님)

 

solved.ac에서 클래스 2를 풀던 중

10989번 '수 정렬하기 3' 에서 막혔다...

 

파이썬으로 풀고 있었는데 자꾸 '시간 초과', '메모리 초과'가 뜨면서 실패했다...

 

하다가 ... 안되서 결국 검색을 했는데 파이썬은 counting sort로 해야 된다고 하는 것 같았다.

근데 counting sort로 해도 안된다...

llm이 짜준 counting sort로 했더니 된다...

왜그런가 봤더니 함수 호출 오버헤드도 있고 사소한 것들까지 다 최적화 해줘야 되는 것 같다.

 

input 대신 sys.stdin.readline이라던지...

입력도 리스트로 받으면 메모리 낭비니까 입력 즉시 처리해주고...

함수 호출 시 스택 프레임 만드는 시간, 리턴어드레스 처리하는 시간...

counting sort에서 누적합 구하는 것도 생략해주고...

 

이런걸 다 고려해야 '맞았습니다!!' 가 뜬다.

 

참고로 파이썬 빌트인 정렬 알고리즘은 Timsort라고 한다... 꼭 정해진건 아니라 바뀔 수도 있지만...

 

파이썬 너무 느리고 메모리도 많이 써서 진지하게 다른 언어로 갈아탈까 고민도 했었지만

이런 것도 배울 수 있고 현실에선 이런 타이트한 제약이 적으니 일단 계속 쓰는걸로...

 

 

 

https://www.acmicpc.net/problem/10989

 

https://github.com/gwangmin/baekjoon/blob/master/solved.ac/class2/10989_%EC%88%98%20%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0%203.ipynb

baekjoon/solved.ac/class2/10989_수 정렬하기 3.ipynb at master · gwangmin/baekjoon