[SSAFYcial] ??? : 숫자 1억 개를 정렬해보시오.

안녕하세요!

벌써 5월입니다,,

요즘 이것저것 하느라 기사가 좀 늦었네요 ㅠㅋㅋ

 

 

저는 요즘 알고리즘 및 자료구조 공부의 필요성을 느끼고

코드트리에서 처음부터 기본기를 다지고 있는데요,

 

정렬 알고리즘을 공부하다가 흥미로운 주제를 만나 소개해보려고 합니다.

그럼 시작합니다!

 

---

 

먼저 짧은 문제를 하나 내보겠습니다.

배열이 하나 있습니다.
이 배열의 원소는 1부터 10억 사이의 임의의 자연수입니다.
그리고 배열의 길이는 1억입니다.

이 배열을 오름차순으로 정렬해야 한다면 여러분은 어떻게 하실 건가요?

 

정말 막막한 문제인 것 같습니다.

 

우리가 흔히 알고 있는 거품 정렬, 선택 정렬, 삽입 정렬 등을 사용한다면 시간 복잡도가 O(N^2)이기 때문에

최악의 경우 컴퓨터는 1억의 제곱인 10경(100,000,000,000,000,000) 번의 연산을 할 것입니다.

 

그런데, 이 문제를 나름 효과적으로 해결할 수 있는 정렬 알고리즘이 있습니다.

그거슨 바로 기수 정렬입니다.

 

기수 정렬

기수 정렬은 맨 뒤에 있는 자릿수 부터 해당 자리수를 기준으로 정렬한 뒤,

점점 앞으로 이동하며 각 자리수를 기준으로 정렬하다가

최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법입니다.

 

먼저 1의 자리수를 기준으로 정렬해보겠습니다.

동그라미 안의 수를 보고 자신의 1의 자리 수와 같은 위치에 차례대로 적어줍니다.

324, 914와 같이 1의 자리수가 똑같다면 순서대로 같은 열에 적어줍니다.

 

 

 

 

정렬을 마쳤으면 위에서 부터 차례대로 적습니다.

 

이번엔 10의 자리를 정렬해보겠습니다.

주의할 점은 1의 자리 정렬을 마친 후 업데이트 된 배열로부터 10의 자리 정렬을 시작해야 하는 것입니다.

과정은 이전과 동일합니다.

 

마지막으로 100의 자리를 정렬해줍니다.

 

이렇게 3번의 과정을 거치고 나니 숫자들이 오름차순으로 정렬되었습니다.

만약 4자리의 숫자라면 어떨까요?

매 자리수마다 분류 작업을 하기 때문에 4번의 과정을 거치면 완전히 정렬될 것입니다.

 

즉, 기수정렬의 시간 복잡도는 O(k * N)입니다.

k는 자릿수를 의미합니다.

 

기수 정렬 구현 코드

1부터 10억까지의 임의의 자연수를 담은 배열을 정렬하는 위의 문제를

Python으로 구현한 코드입니다.

 

max_k = 10
max_digit = 10

n = int(input()) # 총 원소의 개수
arr = list(map(int, input().split())) # 정렬되지 않은 초기의 배열

def radix_sort():
    global arr

    p = 1
    for k in range(max_k): # 0 ~ 9자리
        tmp = [[] for _ in range(max_digit)]
        for elem in arr:
            idx = (elem // p) % 10   
            tmp[idx].append(elem)
        
        arr = []
        for a in tmp:
            for b in a:
                arr.append(b)
        
        p *= 10 

radix_sort()

for a in arr:
    print(a, end=" ")

 

---

다시 아까 문제로 돌아가보죠!

 

배열이 하나 있습니다.
이 배열의 원소는 1부터 10억 사이의 임의의 자연수입니다.
그리고 배열의 길이는 1억입니다.

이 배열을 오름차순으로 정렬해야 한다면 여러분은 어떻게 하실 건가요?

 

 

기수 정렬 알고리즘으로 이 문제를 풀면,

검사해야 할 자릿수가 최대 10자리이므로 

1억 * 10, 총 10억 번의 연산만에 배열을 정렬할 수 있게 됩니다.

이 경우에 O(k * N)은 O(N^2)보다 훨씬 작죠.

 

 

---

 

오늘은 특이한 시간 복잡도를 가진 기수 정렬에 대해 알아보았습니다.

 

물론 길이가 1억인 배열을 정렬할 일이 있겠냐만은,,

각각 상황마다 유용한 정렬 알고리즘이 있으니 이런 개념들도 알아두면 좋을 것 같아요.

 

그럼 다음에도 유익한 기사로 돌아올게요!

안녕~!~!