백준 2751 파이썬(정렬)

시간복잡도 O(nlogn)을 가지는정렬을 사용해야 통과가 가능한 문제이다

1. 파이썬 내장함수 사용(sorted)

2. 퀵정렬

3. 퀵정렬(cache사용없이)

4. 병합정렬

5. 힙정렬

이 다섯가지 정렬방법으로 풀어보았다.

(그리고 시간이 중요한만큼 sys.stdin.readlind으로 입력값을 받았다.)

---

1. 파이썬 기본 내장함수 sorted() 

import sys
n = int(input())
li = []
for _ in range(n):
    li.append(int(sys.stdin.readline()))
for i in sorted(li):
    print(i)

병합정렬을 기반으로 만들어진 함수이며 O(nlogn)의 시간복잡도를 가지는 알고리즘이라고 한다.

일반적으로 직접 함수를 만들어서 사용하는 것보다 효과적이므로 문제에서 별도의 요구가 없다면 파이썬 내장함수를 이용하는 것이 좋다.

통과되었다.

 

2. 퀵정렬(quick sort)

# 2751 수 정렬하기
# 퀵 소트 O(nlogn), 최악의 경우 O(n^2)
# 시간복잡도
import sys

def quick_sort(li):
    length = len(li)
    if length <= 1:
        return li
    else:
        pivot=li[0]
        bigger = [ele for ele in li[1:] if ele > pivot]
        smaller = [ele for ele in li[1:] if ele < pivot]
        return quick_sort(smaller) + [pivot] + quick_sort(bigger)

n = int(input())
li = []
for _ in range(n):
    li.append(int(sys.stdin.readline()))

li = quick_sort(li)

for i in li:
    print(i)

퀵정렬은 시간초과는 안떳는데 메모리초과 오류가 나서 통과하지 못했다.

퀵정렬 함수가 재귀로 돌아갈때마다 bigger, smaller 리스트가 생성되어 cache메모리를 많이 차지하기 때문이라고 생각한다.

위의 코드는 파이썬의 장점을 살려 직관적으로 이해하기 쉽게 만든 코드이지만 메모리를 많이 차지한다는 단점이 있다.

cache메모리를 많이 사용하지 않도록 함수를 정의할 수도 있다.

 

3. 퀵정렬(cache메모리 사용안함)

# 퀵소트 파이썬 코드 case - 1 : 전체코드
# 재귀함수 O
# 리스트 하나만을 사용해서 정렬한다.

def quick_sort(node, first, last):
  def partition(first,last):
    pivot = node[last]
    left = first
    # print(pivot, first,last)    # 확인용
    for right in range(first, last):
      if node[right] < pivot:
        node[left], node[right] = node[right], node[left]
        left += 1
        # print(node)
    node[left], node[last] = node[last], node[left]
    # print()
    # print(node)
    return left

  # 첫번째 노드가 마지막 노드보다 작은 경우, 재귀진행
  if first < last:
    pivot = partition(first, last)
    quick_sort(node, first, pivot - 1)
    quick_sort(node, pivot + 1, last)

import sys
n = int(input())
li = []
for _ in range(n):
    li.append(int(sys.stdin.readline()))

l = len(li)-1
quick_sort(li,0,l)

for i in li:
    print(i)

중간중간 알고리즘이 어떻게 정렬을 수행하는지 확인할 수 있는 확인용 코드가 있다.

역시나 print함수를 이용해서! 

나도 vs코드를 이용해서 디버깅을 잘 해보고 싶다...

결과는 시간초과가 떳다.

 

이유를 생각해보니 퀵정렬은 시간복잡도가 엄연히 O(N^2)이다. 

역순으로 정렬된 데이터의 경우 퀵정렬은 O(nlogn)이 아니라 O(N^2)의 시간복잡도이다.

테스트 입력의 경우 역순으로 된 데이터도 있을것이다.

 

결론적으로 O(nlogn)의 시간복잡도를 갖는 정렬 알고리즘을 원한다면

퀵정렬은 적합하지 않다.

 

4. 병합정렬(merge sort)

#Merge Sort
def merge(array):
    if len(array) <= 1:
        return array
    
    mid = len(array) // 2
    left = merge(array[:mid])
    right = merge(array[mid:])
    
    return merge_func(left, right)

def merge_func(left, right):
    merge_list = []
    left_id, right_id = 0, 0
    
    #case1 left, right
    while len(left) > left_id and len(right) > right_id:
        if left[left_id] > right[right_id]:
            merge_list.append(right[right_id])
            right_id += 1
        else:
            merge_list.append(left[left_id])
            left_id += 1
    
    #case2 letf
    while len(left) > left_id and len(right) <= right_id:
        merge_list.append(left[left_id])
        left_id += 1
    
    #case3 right
    while len(right) > right_id and len(left) <= left_id:
        merge_list.append(right[right_id])
        right_id += 1
    
    return merge_list

import sys
n = int(input())
li = []
for _ in range(n):
    li.append(int(sys.stdin.readline()))

li = merge(li)

for i in li:
    print(i)

병합정렬은 어떤 상황에서도 O(nlogn)의 시간복잡도를 보장한다.

평균적으로는 퀵정렬이 이름처럼 더 빠르게 정렬할 수 있으나

병합정렬은 최악의 경우에도 O(nlogn)의 시간복잡도를 가지니 안정성 부분에서는 더 좋다고 생각한다.

결과는 통과했다.

 

5. 힙 정렬(heap sort)

# 오름차순 정렬
import heapq

def heapsort(iterable):
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, value)
    for i in range(len(heap)):
        result.append(heapq.heappop(heap))
    return result

import sys
n = int(input())
li = []
for _ in range(n):
    li.append(int(stdin.readline()))

li = heapsort(li)
for i in li:
     print(i)

힙정렬도 병합정렬과 같이 시간복잡도 O(nlogn)을 보장하는 정렬 알고리즘이다.

이 정렬을 이해하기 위해서는 힙이라는 자료구조에 대해서 우선적으로 이해가 필요하다. 

파이썬에서 제공하는 heapq 라이브러리를 사용하여 heapify를 시행하였고 그렇게 만들어진 heap에서 하나씩 꺼내서 힙 정렬을 하였다.

 

내 예상이라면 힙정렬은 통과가 되야하는데 시간초과가 떳다.

갑자기 이 짤이 떠오른다.

왜 시간초과가 떳는지 알아보고 해결하는 것보다 다른 해야할것들이 많아서 

이 문제는 여기서 놓아주려 한다.

 

정말 컴퓨터 안에서 어떤 일들이 일어나고 있는지 정말정말 궁금하다...

 

 

참고> 내림차순 힙정렬

# 내림차순 정렬
def heapsort(iterable):
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, -value)
    for i in range(len(heap)):
        result.append(-heapq.heappop(heap))
    return result

import sys
n = int(input())
li = []
for _ in range(n):
    li.append(int(stdin.readline()))

li = heapsort(li)
for i in li:
     print(i)