파이썬 코딩테스트 강좌, 기수 정렬

안녕하세요! 오늘은 파이썬에서 기수 정렬(Radix Sort) 알고리즘에 대해 알아보겠습니다. 기수 정렬은 공간 복잡도와 시간 복잡도가 매우 유리한 정렬 알고리즘 중 하나로, 특히 정수나 문자열과 같은 형태의 데이터를 정렬할 때 유용합니다. 이 강좌에서는 기수 정렬의 원리, 구현 방법, 그리고 실제 문제를 통해 기수 정렬을 사용하는 방법을 자세히 설명하겠습니다.

기수 정렬이란?

기수 정렬은 주어진 숫자의 각 자리수(십의 자리, 백의 자리 등)를 고려하여 정렬하는 방법입니다. 기수 정렬은 다음과 같은 단계로 진행됩니다:

1. 가장 낮은 자리수부터 시작하여 각 자리수를 기준으로 분배합니다.
2. 분배된 수들을 다시 모아서 정렬된 리스트를 만듭니다.
3. 다음 자리수로 이동하여 과정을 반복합니다.

기수 정렬은 일반적으로 두 가지 방식으로 구현됩니다: LSD(Least Significant Digit) 방식과 MSD(Most Significant Digit) 방식. 이 강좌에서는 LSD 방식, 즉 가장 작은 자리수부터 시작하는 기수 정렬에 초점을 맞출 것입니다.

기수 정렬의 시간 복잡도

기수 정렬의 시간 복잡도는 O(nk)입니다. 여기서 n은 정렬할 숫자의 개수, k는 가장 큰 수의 자리수입니다. 기수 정렬은 안정 정렬로 분류되며, 이는 같은 값을 가진 요소의 상대적인 순서가 변하지 않음을 의미합니다.

문제: 기수 정렬을 이용한 정렬

이제 기수 정렬을 적용하여 주어진 정수를 정렬하는 문제를 풀어보겠습니다. 문제는 다음과 같습니다:

문제 풀이 과정

이제 위의 문제를 해결하기 위해 기수 정렬을 구현해보겠습니다. 먼저, 아래와 같이 각 자리수를 기준으로 정렬하는 보조 함수인 counting_sort를 작성하겠습니다. 이 함수는 주어진 자리수를 기준으로 배열을 정렬합니다.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # 정렬된 배열을 저장할 리스트
    count = [0] * 10  # 0~9까지의 숫자를 세기 위한 리스트

    # 현재 자리수에 따라 각 숫자의 개수를 센다
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # 누적합을 통해 각 숫자의 위치를 찾는다
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 정렬된 배열을 생성
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # 정렬된 결과를 원본 배열에 반영
    for i in range(n):
        arr[i] = output[i]

위의 코드에서 counting_sort 함수는 입력 배열에서 각 숫자의 현재 자리수를 검사하여 해당 자리수에 맞는 숫자의 개수를 카운트하고, 누적 합을 통해 정렬된 결과를 생성합니다. 이제 기수 정렬을 구현하는 메인 함수를 작성하겠습니다.

def radix_sort(arr):
    # 배열에서 가장 큰 수를 찾아 자리수를 결정
    max_num = max(arr)

    # 가장 작은 자리수부터 시작하여 정렬
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

이제 기수 정렬의 전체 구현을 살펴보겠습니다.

def radix_sort(arr):
    max_num = max(arr)  # 최대값을 찾는다
    exp = 1  # 자리수의 승수 초기화
    while max_num // exp > 0:  # 최대값의 자리수 만큼 반복
        counting_sort(arr, exp)  # 현재 자리수에 대해 counting_sort 호출
        exp *= 10  # 다음 자리수로 이동

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n  # 정렬된 배열을 저장할 리스트
    count = [0] * 10  # 0~9까지의 숫자를 세기 위한 리스트

    # 현재 자리수에 따라 각 숫자의 개수를 센다
    for i in range(n):
        index = (arr[i] // exp) % 10
        count[index] += 1

    # 누적합을 통해 각 숫자의 위치를 찾는다
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 정렬된 배열을 생성
    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

    # 정렬된 결과를 원본 배열에 반영
    for i in range(n):
        arr[i] = output[i]

# 테스트 코드
arr = [170, 45, 75, 90, 802, 24, 2, 66]
print("정렬 전 배열:", arr)
radix_sort(arr)
print("정렬 후 배열:", arr)

테스트 결과

위의 코드를 실행하면 다음과 같은 결과가 나타납니다:

정렬 전 배열: [170, 45, 75, 90, 802, 24, 2, 66]
정렬 후 배열: [2, 24, 45, 66, 75, 90, 170, 802]

정렬 전의 배열과 정렬 후의 배열을 비교하면, 기수 정렬이 잘 작동한 것을 알 수 있습니다.

기수 정렬의 장점과 단점

장점

• 특정한 조건의 데이터(정수, 문자열 등)에 대해 매우 빠른 성능을 발휘합니다.
• 안정 정렬이기 때문에 같은 값을 가진 요소들의 순서가 보존됩니다.
• 특정 자리수에 관심이 있는 경우 효율적으로 정렬이 가능합니다.

단점

• 메모리를 추가로 소비하며, 원본 배열과 동일한 크기의 배열이 필요합니다.
• 정수나 문자열이 아닌 다른 데이터 타입에는 적합하지 않습니다.
• 데이터의 범위가 매우 큰 경우 시간 복잡도가 증가할 수 있습니다.

마무리

이번 강좌에서는 기수 정렬에 대해 자세히 알아보았고, 이를 통해 배열을 정렬하는 문제를 해결했습니다. 기수 정렬은 특정한 상황에서 매우 유용한 정렬 알고리즘이므로, 알고리즘 시험에서는 자주 등장할 수 있습니다. 따라서, 기수 정렬의 원리와 실제 구현 방법을 명확히 이해하는 것이 중요합니다. 다음 시간에는 또 다른 유용한 정렬 알고리즘이나 데이터 구조에 대해 알아보도록 하겠습니다. 읽어주셔서 감사합니다!