코틀린 코딩테스트 강좌, 기수 정렬

안녕하세요! 오늘은 취업 준비생과 코딩테스트 준비자들이 알아야 할 기수 정렬(Radix Sort)에 대해 알아보겠습니다. 기수 정렬은 정수들을 정렬하는 데 매우 효율적인 알고리즘 중 하나로, 특히 큰 데이터셋에서 그 성능이 빛을 발합니다.

기수 정렬이란 무엇인가?

기수 정렬은 분산 정렬의 일종으로, 정렬할 값들을 개별 자리수로 나누어 처리합니다. 이 방법은 정수형 데이터에 특히 효과적이며, 안정 정렬(stable sort)입니다. 기수 정렬은 대부분의 정렬 알고리즘과 달리 비교 기반이 아니므로, O(nk)의 시간 복잡도를 가집니다. 여기서 n은 정렬할 데이터의 개수이고, k는 가장 큰 수의 자리수입니다.

문제 설명

문제: 주어진 정수 리스트를 기수 정렬 알고리즘을 사용하여 오름차순으로 정렬하라.

다음과 같은 입력이 주어질 때, 기수 정렬을 사용하여 정렬된 결과를 출력해야 합니다.

입력: [170, 45, 75, 90, 802, 24, 2, 66]

출력: [2, 24, 45, 66, 75, 90, 170, 802]

기수 정렬 알고리즘 이해하기

기수 정렬의 기본 아이디어는 각 자리를 기준으로 카운팅 정렬을 반복 사용하는 것입니다. 기수 정렬의 수행 과정을 단계별로 살펴보겠습니다.

1단계: 자리수 분리

각 숫자를 숫자의 자리수(1의 자리, 10의 자리, 100의 자리 등) 별로 나누어 처리합니다. 각 자리수를 처리할 때는 카운팅 정렬을 통해 이 숫자들을 정렬합니다.

2단계: 카운팅 정렬

카운팅 정렬은 특정 자리수를 기준으로 입력 리스트를 정렬하는 방법입니다. 이 방법은 안정성이 확보되기 때문에, 처음에 조정한 상대적인 순서를 유지할 수 있습니다.

3단계: 반복

가장 작은 자리수부터 시작하여, 가장 큰 자리수까지 반복하여 정렬한 후 최종적으로 정렬된 결과를 얻을 수 있습니다.

기수 정렬의 구현 (코틀린 예제)

다음은 코틀린을 사용하여 기수 정렬을 구현한 코드입니다:

fun countingSort(array: IntArray, place: Int) {
    val size = array.size
    val output = IntArray(size)
    val count = IntArray(10)

    for (i in 0 until size) {
        count[(array[i] / place) % 10]++
    }

    for (i in 1 until 10) {
        count[i] += count[i - 1]
    }

    for (i in size - 1 downTo 0) {
        output[count[(array[i] / place) % 10] - 1] = array[i]
        count[(array[i] / place) % 10]--
    }

    for (i in 0 until size) {
        array[i] = output[i]
    }
}

fun radixSort(array: IntArray) {
    val max = array.maxOrNull() ?: return

    for (place in 1 until max + 1 step 10) {
        countingSort(array, place)
    }
}

위 코드는 먼저 카운팅 정렬을 수행하는 countingSort 함수를 정의합니다. 그 후, 주어진 배열의 최대값을 기준으로 자리수를 반복하며 정렬을 진행하는 radixSort 함수를 구현합니다.

코드 설명

countingSort 함수는 주어진 자리수를 기준으로 정렬을 수행합니다.
place는 현재 정렬할 자리수를 나타내며, 1의 자리에서 시작하여 10씩 증가합니다.
count 배열은 각 숫자(0-9)의 출현 빈도를 세는 데 사용됩니다.
최종적으로 output 배열에 정렬된 결과를 저장하고 입력 배열을 업데이트합니다.

기수 정렬의 시간 복잡도

기수 정렬의 시간 복잡도는 O(nk)입니다. 여기서 k는 자리수이며 n은 배열의 크기입니다. 대부분의 다른 비교 기반 정렬 알고리즘은 평균적으로 O(n log n)의 시간 복잡도를 가지므로, 기수 정렬이 훨씬 더 빠른 성능을 보일 때가 많습니다. 특히, 입력 데이터의 크기가 많고 자리수가 적을 때 효과적입니다.

기수 정렬의 한계

기수 정렬은 몇 가지 한계점을 가지고 있습니다:

정수형 데이터에 적합: 이 알고리즘은 정수형 데이터에 특화되어 있으며, 문자열이나 부동 소수점 수에 대해서는 변형된 버전을 필요로 합니다.
범위 제한: 큰 값의 범위를 가지는 정수에 대해서는 메모리 사용량이 증가할 수 있으므로 주의해야 합니다.
메모리 사용: 중간 단계에서 임시 배열을 생성하므로, 메모리 사용량이 많을 수 있습니다.

결론

이번 강좌에서는 기수 정렬에 대해 자세히 알아보았습니다. 기수 정렬은 안정성이 뛰어나고 특정 상황에서 매우 효과적인 정렬 알고리즘입니다. 코딩테스트에서 기수 정렬을 이해하고 올바르게 적용하는 것은 많은 도움이 될 것입니다. 다음에는 다른 정렬 알고리즘에 대해서도 다루어보겠습니다. 감사합니다!