[Python] 백준, 2751(정렬)

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

2751번: 수 정렬하기 2

버블, 단순 선택, 단순 삽입, 셸, 퀵, 병합, 힙 중에 병합 정렬이나 힙 정렬로만 풀리는 시간 복잡도를 갖는 문제다. 퀵 정렬의 경우 꽤 빠른 정렬이기는 하지만, 배열의 종류에 따라서 그 기능이 천차만별이기 때문에 사용에 주의를 해야 한다고 한다. 병합 정렬은 재귀적인 부분에서 이해가 잘 가지 않아서 잠깐 막혔지만, 몇 가지 케이스를 따라가다 보면 이해가 될 수밖에 없는 재귀 알고리즘의 특성상 결국은 이해 완료.

 

재귀는 역시 나름의 손맛이 있다.

 

업로드하는 코드는 2751번의 해결 코드이긴 하지만 병합 정렬을 알고리즘으로 구현한 코드 그 자체이기도 하다. 가끔씩 보면서 복습해주는 게 좋지 않을까 싶다.

 

# PYTHON CODE

import sys
 
n = int(sys.stdin.readline())
s = [int(sys.stdin.readline()) for _ in range(n)]
 
def merge_sort(s):
    if len(s) <= 1:
        return s
 
    mid = len(s) // 2
    left = merge_sort(s[:mid])
    right = merge_sort(s[mid:])
 
    i, j, k = 0, 0, 0
 
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            s[k] = left[i]
            i += 1
        else:
            s[k] = right[j]
            j += 1
        k += 1
 
    while i < len(left):
        s[k] = left[i]
        i += 1
        k += 1
 
    while j < len(right):
        s[k] = right[j]
        j += 1
        k += 1
 
    return s
 
merge_sort(s)
 
for i in s:
    print(i)

위의 알고리즘처럼, 배열을 분할한 뒤 하나로 합치는 형식의 알고리즘을 분할 정복이라고 한단다. 명명된 알고리즘들은 어쩌면 이미 내가 한번쯤은 접한 것들일 수도...?