5일차 때 풀었던 문제가 시간 초과가 떴다!!! 그래서 다시 풀어보기로 하였다...

2751: 수 정렬하기 1

사실 다시 풀어본다기 보다는 다른 풀이를 보며 새로운 풀이법을 익히는... 그런 time...
참고한 블로그는 아래의 블로그이다.
(https://assaeunji.github.io/python/2020-05-06-bj2751/)

저번에 버블 정렬과 삽입 정렬을 공부했다. 그런데 얘네들은 시간 복잡도가 큰 아이들이었고, 2초라는 시간 안에 정렬을 완료하기 위해서는 새로운 정렬 알고리즘이 필요했다. 시간복잡도는 추후에 정리해서 올리겠다!!!

1. 병합정렬

병합 정렬이란 순서가 제멋대로인 배열이 있을 때 이를 정렬하기 위해 분할과 정복 방식을 이용하는 것이다.

• 분할: 데이터를 절반씩 나누어 하나의 데이터가 될 때까지 갔다가
• 정복: 다시 절반씩 합치면서 그 속에서 정렬하는 것

참고한 블로그에서는 분할 단계에서 분할되는 깊이가 logN에 비례하고 각 깊이 별로 분할이 수행되어 합병해야 되는 배열의 수는 많아지지만, 총 원소의 수는 N개로 같으므로 각 깊이별로 수행되는 merge의 시간복잡도는 O(N)이라고 한다. (사실 난 시간복잡도에 대해 정확히 모르는 상태라 log가 왜 나오는지 O가 무엇인지 몰랐다...)

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

참고한 블로그의 전체 코드는 이와 같다. 이제 하나하나씩 분석해보자.

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

먼저 array를 받고 만약 그 길이가 1이면 정렬을 할 필요가 없으니 그대로 반환한다.

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

그 후 재귀함수를 이용해서 분할을 진행한다. 전체 길이를 반으로 쪼개고 왼쪽 부분, 오른쪽 부분을 재귀 함수에 넣는다. 재귀함수를 이용하다보면 전체 길이가 8이라고 했을 때 4->2->1 순으로 분할될 것이다.

 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

이제 분할된 상태에서 비교를 해준다. 일단 i, j, k라는 새로운 변수를 모두 0으로 초기화 해준다. 그 후에 i가 왼쪽의 길이보다 작고, j가 오른쪽의 길이보다 작은 동안의 상황을 if문으로 판단해준다.

그냥 코드를 줄줄 읽는 것보다는 실제 상황을 대입해보자. 하나로 분할이 완료된 상태가 1 5 <- left | right -> 3 6 라고 해보자.

이때 만약 left[i]가 right[j]보다 크면 array[k], 즉 최종 배열의 k 번째가 left[i]가 된다.
1이 3보다 작으면, 전체 배열의 0번째 (현재 k가 0이므로)는 1이 된다. 즉 현재 array 상태는 1만 들어온 상태!

그리고 i에 1을 더해준다. 그럼 left[1] = 5가 된다. 5가 right[0] = 3보다 크므로 else문을 따르게 되고 그럼 현재 array는 1 3 이 들어온 상태!

마찬가지로 j에 1을 더해준다. right[1] = 6이므로 if문을 따르고 그럼 array = 1 3 5 6으로 정렬이 된다. 그리고 이러한 array를 return 문을 활용해 반환하는 것이다.

지금까지 병합정렬을 알아보았다. 블로그 저자는 Pypy의 sorted() 내장함수를 사용하면 시간복잡도가 줄어들어 훨씬 빠르게 답에 접근할 수 있다고 한다...!

오늘도 신기한 알고리즘의 세계 끝!