[백준] 24060 - 알고리즘 수업 - 병합 정렬 1 (파이썬)

1. 문제

 

2. 코드

a, k = map(int, input().split())
l = list(map(int, input().split()))
n = 0
temp = []
tmp = []

def merge_sort(p, r):
    global l
    if p < r:
        q = int((p+r)/2)
        merge_sort(p, q)
        merge_sort(q+1, r)
        merge(p, q, r)

def merge(p, q, r):
    global temp
    tmp = []
    
    i = p
    j = q+1
    
    while i <= q and j <= r:
        if l[i] <= l[j]:
            tmp.append(l[i])
            temp.append(l[i])
            i+=1
        else:
            tmp.append(l[j])
            temp.append(l[j])
            j+=1
    while i <= q:
        tmp.append(l[i])
        temp.append(l[i])
        i+=1
    while j <= r:
        tmp.append(l[j])
        temp.append(l[j])
        j+=1
    
    for i in range(p, r+1):
        l[i] = tmp[i-p]
        
        
merge_sort(0, len(l)-1)

if len(temp) < k:
    print(-1)
else:
    print(temp[k-1])

 

3. 풀이

병합 정렬 문제이다. 해당 문제에 주어진 의사코드를 파이썬으로 잘 변환하기만 하면 된다. 

 

여기서 병합 정렬 (merge sort)란?

분할 정복(divide and conquer) 알고리즘 중 하나이다.

분할 정복 방법이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 후, 그 결과를 모아서 원래의 문제를 해결하는 방법이다. 2개의 문제로 분리하고 각각을 해결하는 방식을 택하기 때문에 순환호출(recursion)을 사용하여 구현되는 경우가 많다.

 

merge sort는 하나의 리스트를 더이상 분할할 수 없을 때까지 두 개로 분할하고 이 부분 리스트들을 정렬한 후, 합치는 방식으로 구현한다.

 

 

merge sort 설명 참고 사이트 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html 

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog