[알고리즘] 백준. # 정렬 2751

O(nlogn)의 복잡도를 가진 정렬 방식으로 구현하라 했는데, 오랜만에 '합병 정렬(merge sort)'을 써서 한 번 구현해 보고자 하였다. (물론 문제에선 내장 함수를 쓰라고 하긴 했다..ㅎㅎ)

재귀 형식으로 구현했는데, 아니나 다를까. 실행시간 초과다..

n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))
    
def combine(ls, start, mid, end):
    s = start
    t = mid+1
    sorted_ls = []
    while True:
        if s > mid:
            sorted_ls+=ls[t:end+1]
            break
        elif t>end:
            sorted_ls+=ls[s:mid+1]
            break
            
        if ls[s]<ls[t]:
            sorted_ls.append(ls[s])
            s+=1
        else:
            sorted_ls.append(ls[t])
            t+=1
        
    for k in range(start,end+1):
        ls[k] = sorted_ls[0]
        sorted_ls.pop(0)
    
    
def merge_sort(ls, start, end):
    mid = (start+end)//2
    
    if start >=end:
        return
        
    merge_sort(ls, start, mid)
    merge_sort(ls, mid+1 , end)
    combine(ls, start, mid, end)
    return ls

sls = merge_sort(ls, 0, n-1) #sls: sorted ls
for l in sls:
    print(l)

좀 더 최적화를 시켜보고 싶지만,, 아직 갈 길이 멀기에,,

(반복문을 이용해 구현하거나(가능한가?), C나 C++을 사용하면 훨씬 빠를 것 같긴하다.)

 

다음은 내장 함수를 이용한 코드이다. 

n = int(input())
ls = []
for i in range(n):
    ls.append(int(input()))
    
ls.sort()
for l in ls:
    print(l)

list 내부 메소드인 sort()로 손쉽게 구현이 가능하다. 근데 이것도 python3로 돌리니 시간초과가 떴다. 

pypy3으로 돌리니 통과했다. 찾아보니 pypy3가 python을 빠르게 구동시키기 위해 만든 언어란다. JIT(just in time) compiler로 바로 기계어 또는 저급언어로 번역 하도록 하는 방식이라던데, 백준 테스트에서 자주 써야겠다. 

 

 

합병 정렬(merge sort)에 대해 간단히 설명하자면, 합병 정렬은 '분할 정복(divide and conquer)' 기법을 사용한 정렬 방식이다. 

분할 정복에 대해 설명하자면, 이를 테면 이런 거다.

 

 

1000개 이상의 매우 많은 동전을 주며 동전의 개수를 세어보라고 한다면 당신은 어떤 방식으로 셀 것인가.

 

1000개 이상의 매우 많은 동전을 주며 동전의 개수를 세어보라고 한다면 당신은 어떤 방식으로 셀 것인가.

 

필자는 10개씩 묶어서 세고 10개 짜리 묶음을 다시 10개씩 묶어서 100개 묶음으로 만드는 작업을 여러 번 반복하여 개수를 셀 것이다. 이게 바로 분할 정복 기법을 가장 잘 보여주는 예시라 생각한다.

 

1) 인간의 인지 능력의 한계로 개수를 한 번에 파악할 수 있는 수가 정해져 있다. (한 번에 풀 수 없는 어려운 문제 봉착)

 

2) 따라서 우리가 셀 수 있는 단위만큼을 계산한다. (문제를 풀 수 있는 단위까지 '분할'한다.)

 

3) 계산된 결과를 더 큰 단위의 계산에 이용하여 풀어낸다. (한 번에 풀기 어려웠던 문제를 단계를 밟아가며 '정복'함)

 

 

이 일련의 분할, 정복 과정이 합병 정렬에도 녹아들어가 있다. 

전체적인 틀은 주어진 수열을 정렬하기 위해 수열을 작은 단위로 분할한다. 여기서 분할은 보통 반으로 나눈다. 계속 나누다 보면, 가장 마지막에 1개:2개 이렇게 나눠지게 될 것이다. 1개의 경우 정렬할 필요가 없고, 2개는 서로 비교하여 앞의 값이 더 크면 순서를 바꾸면 된다.(오름차순의 경우) 즉, 매우 쉬운 문제가 된다. 이렇게 정렬된 짧은 수열을 윗 단계로 넘겨 같은 방식으로 정렬된 수열끼리 비교하도록 한다. 

 

말로 설명하는 데에는 한계가 있으니, 예시를 살펴보자. 

 

[8, 4, 5, 2, 6, 7, 3, 1]이라는 수열이 주어졌다고 할 때, 분할 과정은 다음과 같다. 

분할 과정

 

분할이 최소 단위까지 이뤄졌으면, 이제 정복 단계가 시작된다. 필자는 인덱스를 이용해 쪼개졌던 두 부분을 전체 리스트에서 참조하여 숫자를 비교한 후 새 리스트에 정렬된 상태로 넣어주었다. 그리고 이 정렬된 새 리스트를 비교할 수를 접근하는 데 사용했던 인덱스로 원래 리스트에 업데이트 시켜주었다. 

다음과 같은 과정으로 정렬이 이뤄지게 된다. 

 

시간 복잡도를 대략 계산해 본다면, 

n개의 데이터가 주어졌을 때, 반으로 나누는 작업을 원소가 하나남을 때까지 계속한다. 이 걸 몇 번 했는지에 따라 정복 과정에서 몇 번의 단계를 거쳐야 하는 지 알 수 있다. 

식을 세워보면,

 

$n * {\frac{1}{2}}^x$ = 1

$n = 2^x$

$x = log_2{n}$

즉, $log_2{n}$의 단계가 나온다. 

 

위의 예시로 살펴보면 $log_2{8}$ = 3이므로, 3단계(원소의 개수 1개 짜리, 2개 짜리, 4개 짜리)가 되겠다. 

 

여기서 각 단계 별로 전체 n개의 요소들에 대해 loop를 돌며 비교하고 이를 새 리스트에 삽입하고 다시 원래 리스트를 업데이트 하면, (loop index increment 1 + compare 1+ insert 1+ update 1)*n = 4n 정도의 연산이 일어날 것이다. 

 

각 단계별로 이 연산이 일어나기에 전체 복잡도는 4n*$log_2{n}$이 되고, big O 표기법으로 표기하면, O(nlogn)이 되겠다. 

 

물론 이는 대략 계산한 값이기에 오차가 있을 수 있다.