"이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편 13장의 써머리입니다."

13. 정렬(Sort)

1) 정렬 개념

정렬(sort) : 사용자가 정의한 순서로 데이터를 나열하는 것

정렬이 필요한 이유

데이터를 정렬하면 원하는 데이터를 쉽게 찾기가 가능(eg. 이진 탐색 트리)

삽입 정렬(Insertion Sort)

데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬

삽입 정렬의 시간 복잡도는 최악의 경우 O(N^2), 최선의 경우 O(N)

병합 정렬(Merge Sort)

정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬

* 이런 방식을 분할 정복(Divide and Conquer)이라고 함

* 병합 정렬의 핵심 : ‘병합할 때 부분 정렬하는 부분을 어떻게 구현해야 하는가?’

병합 정렬의 시간 복잡도

병합 정렬의 성능은 결국 병합 횟수가 결정

나누는 횟수 : logN
합치는 횟수 : NlogN(N개를 병합하는 과정을 logN번 진행)     $\therefore$ O(NlogN)

힙 정렬(Heap Sort)

힙이라는 자료구조를 사용해 정렬
힙 정렬을 하기 위해서 먼저 주어진 데이터로 힙을 구축해야 함

힙이란?

힙은 특정 규칙이 있는 이진 트리, 규칙에 따라 최대 힙, 최소 힙으로 나눔

최대 힙 : 부모 노드가 자식 노드보다 큼
최소 힙 : 부모 노드가 자식 노드보다 작음

* max_heapify() : 특정 노드가 최대 힙의 규칙을 만족하지 못하면 힙을 구축하는 과정을 아래로 내려가면서 반복하는 동작

힙 정렬 과정 : 최대 힙

최대 힙에서 힙 정렬은 루트 노드가 가장 큰 값이므로 루트 노드의 값을 빼서 저장하기만 하면 됨

But, 루트 노드의 값을 뺀 이후 최대 힙을 유지하는 것이 중요

힙 정렬의 시간 복잡도

데이터는 N개이고 각 데이터에 대해 힙 정렬을 수행하면 O(N*logN)

우선순위 큐

우선순위가 높은 데이터부터 먼저 처리하는 큐 즉, 우선순위에 따라 pop을 하는 큐

우선순위 큐의 내부 동작은 힙과 매우 유사하므로 우선순위를 구현할 때 힙을 활용하는 것이 효율적

우선순위 큐의 핵심 동작 : 우선순위가 높은 데이터를 먼저 pop하는 것

최소 힙, 최대 힙은 특정 값을 루트 노드에 유지하는 특징이 있고, 이는 우선순위 큐의 핵심 동작과 맞아 떨어지므로 힙을 활용하면 우선순위 큐를 효율적으로 구현할 수 있다는 것을 알 수 있음

힙으로 우선순위 큐 구현하기

데이터 자체에 우선순위를 직접 정하고 싶다면 튜플 형태로 (우선순위, 데이터)를 heappush()에 전달

heapq의 시간 복잡도

힙 정렬의 삽입, 삭제 연산의 효율과 완전히 동일

원소의 개수가 N이라고 할 때, 시간 복잡도는 heapify()는 O(N)이고, heappush() / heappop() 둘 다 O(logN)

위상 정렬(Topological Sort)

일의 순서가 있는 작업을 순서에 맞춰 정렬하는 알고리즘

위상 정렬은 일의 순서가 중요하므로 반드시 간선의 방향이 있어야 함

위상 정렬과 진입차수

위상 정렬은 자신을 향한 화살표 개수를 진입차수로 정의하여 진행

위상 정렬의 시간 복잡도

모든 정점의 간선을 딱 한 번씩만 지나므로 시간 복잡도는 O(|V|+|E|)

계수 정렬(Counting Sort)

계수 정렬은 데이터에 의존하는 정렬 방식, 데이터의 빈도수로 정렬
* 결과를 확인할 때 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 출력

계수 정렬의 한계

계수 정렬의 핵심 동작은 빈도수를 세어 빈도수 배열에 저장하는 것
→ 빈도수 배열에 저장할 값의 범위가 듬성듬성 있거나, 음수가 있으면 계수 정렬을 하기 매우 곤란함

계수 정렬의 시간 복잡도

값의 최솟값~최댓값 범위 크기가 K라면 빈도수 배열에서 K + 1만큼 탐색해야 하므로 계수 정렬의 시간 복잡도는 O(N+K)

2) 몸 풀기 문제

문제 54) 계수 정렬 구현하기

인자로 받은 문자열 s를 계수 정렬로 정렬하여 반환하는 함수 구현

def solution(s):
  count = [0] * 26
  res = ""
  
  for i in s:
    count[ord(i) - ord('a')] += 1
  
  for i in range(len(count)):
    if count[i] > 0:
      for j in range(count[i]):
        alp = i + ord('a')
        res += chr(alp)
  
  return res

assert solution("hello") == "ehllo"
assert solution("algorithm") == "aghilmort"

문제 55) 정렬이 완료된 두 배열 합치기

이미 정렬이 완료되어 있는 두 배열 arr1, arr2를 받아 병합 정렬하는 함수 구현

def solution(arr1, arr2):
  res = []
  i, j = 0, 0
  
  while i < len(arr1) and j < len(arr2):
    if arr1[i] < arr2[j]:
      res.append(arr1[i])
      i += 1
    else:
      res.append(arr2[j])
      j += 1
  
  res.extend(arr1[i:])
  res.extend(arr2[j:])
  
  return res

assert solution([1, 3, 5], [2, 4, 6]) == [1, 2, 3, 4, 5, 6]
assert solution([1, 2, 3], [4, 5, 6]) == [1, 2, 3, 4, 5, 6]

3) 합격자가 되는 모의 테스트

문제 56) 문자열 내 마음대로 정렬하기

문자열로 구성된 리스트 strings와 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하기

def solution(strings, n):
  
  return sorted(strings, key=lambda s: (s[n], s))

assert solution(["sun", "bed", "car"], 1) == ["car", "bed", "sun"]
assert solution(["abce", "abcd", "cdx"], 2) == ["abcd", "abce", "cdx"]

문제 57) 정수 내림차순으로 배치하기

정수 n을 받아 n의 각 자릿수를 내림차순으로 정렬한 새로운 정수 반환

def solution(n):
  lists = list(map(int, str(n)))
  
  lists.sort(reverse=True)
  
  res = int(''.join(map(str, lists)))
  
  return res

assert solution(118372) == 873211

문제 58) K번째 수

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때 k번째에 있는 수를 구하려고 함. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 주어질 때 commands의 모든 원소에 대하여 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 반환하는 함수 작성

def solution(ary, commands):
  res = []
  
  for c in commands:
    i, j, k = c
    
    sort_ary = sorted(ary[i-1:j])
    
    res.append(sort_ary[k-1])
  
  return res

assert solution(
  [1, 5 ,2, 6, 3, 7, 4], 
  [[2, 5, 3], [4, 4, 1], [1, 7, 3]]) == [5, 6, 3]