알고리즘 - 정렬

해시, 큐/스택, 힙 자료구조에 이어 이번에는 알고리즘에 대해 처음으로 접해볼 시간이다.

그 중 이번에 살펴볼 것은 정렬 알고리즘이다. 정렬을 하는 알고리즘이 굉장히 많은 것으로 알고있지만 이 시리즈의 경우 코딩테스트를 위한 정리본이므로 여러 정렬 알고리즘에 대해 다루는 대신, 실제 코딩테스트에서 쓰이는 방법 위주로 정리해보겠다.

자료구조 / 알고리즘에 대한 간략한 설명

정렬 알고리즘에는 정말 많은 알고리즘이 존재한다. 버블 정렬, 삽입 정렬, 병합 정렬, 선택 정렬, 퀵 정렬 등....

이 중 간단하게 삽입 정렬과 병합 정렬에 대해서만 알아보자.

삽입 정렬이란 하나하나의 요소를 자기 위치에 삽입시키는 정렬 방식이다.

예를 들어 주어진 리스트가 [1, 2, 3, 7, 5, 4] 꼴이라면 오름차순 기준 [1, 2, 3, 7] 까지가 이미 정렬이 되어있고 5와 4만을 넣으면 되므로 5의 위치를 탐색하여 3과 7 사이에 삽입하게 된다.

그렇게 남은 리스트는 [1, 2, 3, 5, 7]이 되며 이후 4의 위치를 탐색하여 3과 5 사이에 이를 삽입, 전체 리스트가 정렬되는 방식이다.

대충 보아도 하나하나의 위치를 찾아 넣어준다는 점에서 최악의 시간 복잡도가 $O(N^2)$ 으로 굉장히 느려보이지만 이미 부분 정렬된 경우, 시간 복잡도가 $O(N)$으로 굉장히 빠르다는 장점을 가진다.

병합 정렬이란 주어진 배열을 정렬된 여러 하위 배열로 나눈 뒤, 두 개의 포인터를 이용하여 이들을 병합하는 정렬 방식이다.

예를 들어 주어진 리스트가 [1, 3, 9, 4, 5, 7] 이라면 이를 부분 정렬된 하위 배열, [1, 3, 9], [4, 5, 7] 로 먼저 나눈 뒤 두 개의 포인터를 이용하여 1과 4를 비교, 1을 최종 배열에 삽입하고 이후 다시 3과 4를 비교하는 방식으로 하위 배열을 병합하는 방식이다.

별도의 분할 과정이 요구되기에 시간 복잡도는 최선과 최악 모두 $O(NlogN)$을 가지게 된다.

이 두 가지 정렬 알고리즘을 합하여 만든 것이 바로 파이썬 리스트가 기본적으로 채택하는 Timsort 정렬 방식이다.

Timsort 정렬이란 병합 정렬과 마찬가지로 주어진 배열을 먼저 정렬된 여러 하위 배열로 나눈 뒤, 특정 크기 이하의 하위 배열의 경우 삽입 정렬 과정을 통해 다른 하위 배열과 합치는 과정을 거치는 알고리즘이다.

예를 들어 [1, 3, 5, 2, 7, 6] 의 경우 [1, 3, 5], [2, 7], [6]으로 먼저 나눈 뒤 삽입 정렬 과정을 통해 2와 7 사이에 6을 삽입, [1, 3, 5]와 [2, 6, 7]의 두 하위 배열을 만들어 병합 정렬을 수행하게 된다.

이러한 알고리즘은 실제 세계에서 부분 정렬된 경우가 훨씬 많기에 이를 최대한으로 활용하기 위함이며 너무 많은 하위 배열이 생겨날 경우 포인터를 통한 병합 정렬 과정에서 시간이 많이 소요되기에 이를 해결하기 위해 하위 배열의 크기 제한을 걸어놓은 것이다.

---

여러가지 파이썬 구현 방식

1) 파이썬 정렬 이용

위 Timsort 정렬을 그대로 이용하는 것이 파이썬의 sorted() 혹은 list.sort() 방식이다. 그 파라미터에 대해서만 간단히 알아보자.

• key=None
  정렬 기준을 결정할 수 있게 해주는 파라미터이다.
  해당 값 뿐만 아니라 해당 값이 배열인 경우 그 크기를 통한 비교, 배열의 n번 째 요소를 통한 비교, 혹은 해당 값이 다른 배열에서 가지는 값을 통한 비교 등 다양한 활용이 가능하다.

  # 배열 크기 기준
  sorted(Iterable, key=len)
  
  # Lambda 함수 이용
  sorted(Iterable, key=lambda x:x[0])
  
  # 여러 조건 기준
  sorted(Iterable, key=lambda x:(x[0], len))

• reverse=True
  오름차순과 내림차순을 결정하게 해주는 파라미터이다.
  

2) functools.cmp_to_key 이용

위 정렬을 통해 거의 대부분의 문제가 해결이 가능하지만 특수한 경우가 존재한다.

바로 비교 기준이 "특정 값"만으로 표현되지 않는 경우이다. 예를 들어 두 값의 비교 시 그저 두 값의 크기를 비교하는 것이 아니라 두 값을 이어붙인 순서가 중요한 경우.

예를 들어 3과 34의 비교 시 각 숫자의 크기를 비교하는 것이 아니라 두 숫자를 결합한 순서에 따라 334와 343을 비교하는 등의 경우이다.

혹은 비교 기준이 복잡하게, 동적으로 결정되는 경우이다. 예를 들어 두 문자열의 크기가 동일한 경우 어떤 조건을 비교하고, 다른 경우 다른 조건을 비교하는 식이다.

정렬 과정에서 결국 필요로 하는 것은 key function이며 cmp_to_key는 cmp(compare) function을 key function으로 바꾸어주는 역할을 하게 된다.

cmp_to_key란 결국 커스텀 정렬 기준 함수로 더 다채로운 비교를 위한 tool 이다.
나만의 "비교 함수"를 정렬에서 사용할 수 있는 "key 함수"로 바꾸어 주는 tool.

arr = ["ABC", "BCDF"]

# 두 문자열의 크기가 동일한 경우 1번 째 요소를, 아닌 경우 2번 째 요소를 비교하도록 해보자.
def cmp(a, b):
	"""Compare Function. Large -> Positive / Equal -> 취급 X / Small -> Negative"""
    if len(a) == len(b):
    	return 1 if a[0] > b[0] else -1
    else:
    	return 1 if a[1] > b[1] else -1

cmp(arr[0], arr[1])
>>> -1

정렬을 하기 위한 "비교 함수"를 위처럼 정의해보았다. 두 값이 동일한 경우에 대한 처리를 하지는 않았지만 편의상 무시하자. 이제 이와 같은 비교 방식을 통해 특정 배열을 정렬하고자 하면 문제가 발생한다.

sorted(key=None)은 cmp_function이 아니라 key function을 받는다는 점.

두 요소를 받는 비교 함수를 통해 두 값을 비교하지 않고 두 값에 각각 key function을 적용시킨 후 나온 두 반환값을 비교하는 방식으로 정렬하도록 설계되어 있다.

이 간극을 메꿔주는 것이 cmp_to_key이다.

from functools import cmp_to_key

def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K

그 내용을 살펴보면 우리가 만든 cmp_function을 당장 적용시키지 않고 이를 가지고 있는 별도의 클래스 K를 생성해 반환함을 알 수 있다. 이 클래스 K는 cmp_function을 이용하여 여러 가지 비교 연산을 하도록 설계되어 있어 정렬 시 key function 적용 이후 비교 과정에서 클래스 K 간의 비교 연산이 작동, cmp_function이 이용되는 것이다.

# 기존 정렬 방식 -> key function 적용 이후 비교
arr = ["ABC", "BCDF"]
sorted(arr, key=lambda x: x[0])
-> "ABC"[0] => "A"
-> "BCDF"[0] => "B"
-> 이후 비교 => 더 작음
-> 오름차순 유지

# cmp 정렬 방식 -> 별도의 클래스 K 생성 이후 비교 시 cmp function 이용
arr = ["ABC", "BCDF"]
sorted(arr, key=cmp_to_key(cmp))
-> cmp_to_key(cmp)("ABD") => K("ABD")
-> cmp_to_key(cmp)("BCDF") => K("BCDF")
-> 이후 K 클래스 간 비교 => 자체 cmp 함수를 이용한 비교 => 더 작음
-> 오름차순 유지

이처럼 cmp_to_key 변환 함수는 별도의 클래스 K 인스턴스만을 생성하게 되는 것이다.

---

프로그래머스 문제 풀이

1) K번째수

단순한 정렬 문제로, 특정 구간을 잘라 정렬한 뒤, k번 째 수를 구하는 문제이다.

def solution(array, commands):
    # for command in commands for i,j,k in command 로 
    # 이중 컴프리헨션을 사용했었음.
    # TypeError: cannot unpack non-iterable int object
    return [sorted(array[i-1:j])[k-1] for i,j,k in commands]
    
solution([1, 5, 2, 6, 3, 7, 4], [[2, 5, 3], [4, 4, 1], [1, 7, 3]])
>>> [5, 6, 3]

첫 풀이 시 튜플을 이용한 컴프리헨션 사용법을 잘못 알아 에러를 냈지만 금방 고쳐 풀어내었다 !

2) 가장 큰 수

별도의 정렬 기준을 이용하여 가장 큰 수를 구하는 문제이다. 앞서 설명한 3과 34의 비교 문제.

def solution(numbers):
    numbers = sorted(list(map(str, numbers)), key=lambda x: x*3, reverse=True)
    if numbers[0] == "0":
        return "0"
    return "".join(numbers)
solution([3, 30, 34, 5, 9])
>>> '9534330'

처음 cmp_to_key를 모를 때 풀어낸 풀이이다. 별도의 비교 함수 없이 알고리즘적으로 key function으로 x*3을 이용, 333과 343434를 비교하는 방식으로 풀어내었다.

from functools import cmp_to_key
# 정렬용 커스텀 콜백 함수.
## 인자를 받아 비교 방식 상 더 크면 양수, 더 작으면 음수, 같으면 0을 반환하도록 만들면 된다.
def solution_good(numbers):
    
    def cmp(a:int, b:int):
        return int(str(a) + str(b)) - int(str(b) + str(a))
    
    numbers = sorted(numbers, key=cmp_to_key(cmp), reverse=True)
    
    if numbers[0] == 0:
        return "0"
    return "".join(list(map(str, numbers)))

solution_good([3, 30, 34, 5, 9])

이후 cmp_to_key를 이용하여 풀어낸 풀이. "별도의 비교 함수"만 만들어주면 된다는 점에서 사용법이 헷갈리기는 했지만 어렵지는 않았다.

3) H-Index

n개의 논문이 n번 이상 인용된 n의 최댓값을 찾아내는 문제이다.

# H-index(Y축), cnt(X축)으로 생각
def solution(citations):
    cnt = 0
    citations.sort(reverse=True)
    for cite in citations:
        H_index = cite
        cnt += 1
        if cnt == H_index:          # x = y 에 맞닿는 경우
            return H_index
        elif cnt > H_index:         # x = y 아래로 꺼지는 경우
            return cnt-1
    return cnt                      # x = y 위에만 머무는 경우
solution([5, 4, 1, 1])
>>> 2

한 번의 정렬 과정 이후 스캐닝하는 방식으로 풀어내었다. 이후 다듬은 방식이 아래 방법.

def solution_good(citations):
    return max(min(idx+1, cite) for idx, cite in enumerate(sorted(citations, reverse=True)))

min 함수를 이용하여 모든 점에 대해 x=y 로의 Projection을 진행, 그 중 최댓값을 뽑아내는 방식이다.

예시 문제가 세 문제밖에 되지 않아 아직까지 전체적인 감이 잡히지 않은 것 같다.... 이후 더 풀게되면 추가하는 걸로 !