백준 정렬 2751번

안녕하세요. GDSC 머신러닝 멤버 김민찬입니다.
파이썬은 내장되어 있는 함수가 많아, 이를 잘 활용하면 문제를 쉽게 해결할 수 있을 것 같습니다.

sort( )

아래는 제가 문제를 해결한 과정입니다.

n = int(input()) # 수의 개수

num_list = []
for i in range(n):
    num_list.append(int(input()))

num_list.sort()
# sort 함수를 통해 오름차순으로 정렬 내림차순 정렬은 (reverse=True)
# sorted는 순서대로 정렬, 정렬된 리스트를 반환 ex) y = sorted(x)

for i in num_list:
    print(i)

합병 정렬 (Merge sort)

문제를 너무 쉽게 해결한 것 같아서, 다른 방법에 대하여 찾아보았는데, 이 문제를 해결하기 위한 다른 방법 중 하나로 합병 정렬이 있다는 것을 알게 되었습니다.

합병 정렬의 알고리즘은 다음과 같습니다.

1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다.
    이 때, 원소가 들어있지 않거나 한 원소만 든 리스트는 정렬된 것과 같다.

2. 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다.
    마지막 남은 부분리스트가 정렬된 리스트이다.

이를 간단하게 설명하면,
리스트가 원소가 한 개 혹은 0개인 부분리스트가 될 때까지 균등한 크기로 1/2씩 반복적으로 분할(divide)하고, 이를 결합(combine)하는 과정에서 정렬(conquer)하는 것입니다.
이 때, 두 리스트를 합병하는 과정에서 각 리스트의 첫번째 값부터 비교해가며 더 작은 값을 새로운 리스트로 옮기는 과정으로 진행됩니다.

아래는 제가 참고한 합병 정렬을 통해 2751번을 해결하는 코드입니다.

def merge_sort(array):
    if len(array)<=1:
        return array

    # 재귀함수를 이용해서 끝까지 분할
    mid = len(array)//2
    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])

    i,j,k = 0,0,0

    # 분할된 배열끼리 비교
    while i<len(left) and j <len(right):
        if left[i]<right[j]:
            array[k] = left[i]
            i += 1
        else:
            array[k] = right[j]
            j += 1
        k+=1

    # 먼저 끝났을 때
    if i==len(left):
        while j < len(right):
            array[k] = right[j]
            j+=1
            k+=1
    elif j==len(right):
        while i < len(left):
            array[k] = left[i]
            i+=1
            k+=1
    return array

n=int(input())
num_list = []

for i in range(n):
    num_list.append(int(input()))

num = merge_sort(num)

for i in num:
    print(i)

참고자료
https://assaeunji.github.io/python/2020-05-06-bj2751/
https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

	김민찬
	하면 하지