안녕하세요! 오늘은 파이썬에서 기수 정렬(Radix Sort) 알고리즘에 대해 알아보겠습니다. 기수 정렬은 공간 복잡도와 시간 복잡도가 매우 유리한 정렬 알고리즘 중 하나로, 특히 정수나 문자열과 같은 형태의 데이터를 정렬할 때 유용합니다. 이 강좌에서는 기수 정렬의 원리, 구현 방법, 그리고 실제 문제를 통해 기수 정렬을 사용하는 방법을 자세히 설명하겠습니다.
기수 정렬이란?
기수 정렬은 주어진 숫자의 각 자리수(십의 자리, 백의 자리 등)를 고려하여 정렬하는 방법입니다. 기수 정렬은 다음과 같은 단계로 진행됩니다:
- 가장 낮은 자리수부터 시작하여 각 자리수를 기준으로 분배합니다.
- 분배된 수들을 다시 모아서 정렬된 리스트를 만듭니다.
- 다음 자리수로 이동하여 과정을 반복합니다.
기수 정렬은 일반적으로 두 가지 방식으로 구현됩니다: LSD(Least Significant Digit) 방식과 MSD(Most Significant Digit) 방식. 이 강좌에서는 LSD 방식, 즉 가장 작은 자리수부터 시작하는 기수 정렬에 초점을 맞출 것입니다.
기수 정렬의 시간 복잡도
기수 정렬의 시간 복잡도는 O(nk)입니다. 여기서 n은 정렬할 숫자의 개수, k는 가장 큰 수의 자리수입니다. 기수 정렬은 안정 정렬로 분류되며, 이는 같은 값을 가진 요소의 상대적인 순서가 변하지 않음을 의미합니다.
문제: 기수 정렬을 이용한 정렬
이제 기수 정렬을 적용하여 주어진 정수를 정렬하는 문제를 풀어보겠습니다. 문제는 다음과 같습니다:
문제 설명
정수의 배열이 주어질 때, 기수 정렬을 사용하여 이 배열을 오름차순으로 정렬하는 프로그램을 작성하세요.
입력
- 정수의 배열:
[170, 45, 75, 90, 802, 24, 2, 66]
출력
오름차순으로 정렬된 배열을 출력하세요.
문제 풀이 과정
이제 위의 문제를 해결하기 위해 기수 정렬을 구현해보겠습니다. 먼저, 아래와 같이 각 자리수를 기준으로 정렬하는 보조 함수인 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]
정렬 전의 배열과 정렬 후의 배열을 비교하면, 기수 정렬이 잘 작동한 것을 알 수 있습니다.
기수 정렬의 장점과 단점
장점
- 특정한 조건의 데이터(정수, 문자열 등)에 대해 매우 빠른 성능을 발휘합니다.
- 안정 정렬이기 때문에 같은 값을 가진 요소들의 순서가 보존됩니다.
- 특정 자리수에 관심이 있는 경우 효율적으로 정렬이 가능합니다.
단점
- 메모리를 추가로 소비하며, 원본 배열과 동일한 크기의 배열이 필요합니다.
- 정수나 문자열이 아닌 다른 데이터 타입에는 적합하지 않습니다.
- 데이터의 범위가 매우 큰 경우 시간 복잡도가 증가할 수 있습니다.
마무리
이번 강좌에서는 기수 정렬에 대해 자세히 알아보았고, 이를 통해 배열을 정렬하는 문제를 해결했습니다. 기수 정렬은 특정한 상황에서 매우 유용한 정렬 알고리즘이므로, 알고리즘 시험에서는 자주 등장할 수 있습니다. 따라서, 기수 정렬의 원리와 실제 구현 방법을 명확히 이해하는 것이 중요합니다. 다음 시간에는 또 다른 유용한 정렬 알고리즘이나 데이터 구조에 대해 알아보도록 하겠습니다. 읽어주셔서 감사합니다!