코딩 끝에 낙이 온다 코딩 끝에 낙이 온다

수 정렬하기 2와 같은 문제이나 이번엔 메모리 제한이 8MB로 정해진 문제이다. 전에 사용했던 합병 정렬을 제출했으나 역시나 될리가 없었다. 질문 검색을 해본 결과 가장 많은 사람들이 사용하는 것이 계수 정렬이었다. 그래서 계수 정렬을 알아봤는데,꽤나 빠른 알고리즘이었다 n 시간 복잡도를 가지면서도, 아주 간결한 코드였다.다음은 내가 작성한 코드. 열심히 짠 코드였지만,역시나 메모리 초과. 이번엔 누적합을 제외한 코드를 제출해봤지만 역시나 실패였다. 지푸라기라도 잡아보자는 심정으로 파이썬으로 제출해봤다. 그런데 이게 왠걸?? 맞았다.이번으로 알게 된 교훈은 pypy는 빠르지만 메모리 소모가 크다는 것!

컴퓨터의 창시자 폰 노이만이 개발한 정렬 알고리즘. 퀵 정렬과 함께 O(n log n)의 시간복잡도를 가지는 빠른 알고리즘 중의 하나이다. 퀵 정렬과 마찬가지로 분할 정복을 이용하는 알고리즘으로 최악의 경우 n^2의 시간복잡도를 가지는 퀵 정렬과 달리, 병합 정렬은 모든 경우에 n log n의 시간복잡도를 보장한다. 대략적인 절차를 설명하면 다음과 같다. 1.들어온 배열을 우선 반으로 쪼갠다.(홀수인 경우 반올림 또는 반내림한다) 2.나뉘어진 부분 각각을 다시 크기가 1이 될 때까지 재귀적으로 쪼갠다. 3.요소가 하나가 되면, 나뉘어진 부분끼리 비교하여,합치는 동시에 정렬을 진행한다. 4.위 과정을 재귀적으로 되돌아가 나뉘어진 부분을 각각 다시 정렬하며 합친다. 5.전부 합쳐지면 최종적으로 정렬된 배열이..

무작위로 입력된 소문자 영단어를 길이 순으로 정렬하되 같은 길이면 사전순으로 나열해야하는 문제이다. 단, 길이가 같으면 한 번만 출력해야 한다. import time import math def mergesort(entries): if isinstance(entries,list) and len(entries) > 1 : pivot = math.floor(len(entries)/2)-1 first = mergesort(entries[:pivot+1]) second = mergesort(entries[pivot+1:]) return merge(first,second) else: return entries def merge(first,second): unit=[] if not isinstance(first,l..