C# 코딩테스트 강좌, 기수 정렬

안녕하세요! 오늘은 기수 정렬(Radix Sort)의 개념과 함께 C#을 이용한 구현 방법에 대해 알아보겠습니다. 기수 정렬은 비정렬 데이터를 정렬하는 효율적인 방법 중 하나로, 특히 정수가 차지하는 범위가 제한적일 때 특히 유용한 알고리즘입니다.

1. 기수 정렬이란?

기수 정렬은 자릿수의 위치에 따라서 숫자를 정렬하는 방식으로, 일반적으로 LSD(Least Significant Digit) 방식과 MSD(Most Significant Digit) 방식으로 나뉩니다. L를 사용하면 가장 낮은 자릿수부터 정렬하게 되고, M로 시작하면 가장 높은 자릿수부터 정렬됩니다.

2. 기수 정렬의 동작 원리

기수 정렬의 작동 방식은 다음과 같습니다:

가장 낮은 자릿수부터 시작하여 각 자릿수를 기준으로 데이터를 정렬합니다.
정렬을 반복하여 가장 높은 자릿수까지 진행합니다.
이 과정에서 안정적인 정렬 알고리즘, 예를 들어 계수 정렬(Counting Sort)을 사용하여 자릿수별로 정렬합니다.

3. 기수 정렬의 시간 복잡도

기수 정렬의 시간 복잡도는 O(d * (n + k))입니다. 여기서 d는 숫자의 자릿수, n은 정렬할 숫자의 개수, k는 0부터 최대 자릿수까지의 숫자 범위입니다. 가장 큰 장점 중 하나는 기수 정렬이 안정적이라는 점입니다.

4. 기수 정렬 문제 풀이 예제

이번에는 기수 정렬을 사용하여 특정 숫자 목록을 정렬하는 문제를 풀어보겠습니다.

문제 설명

주어진 정수 목록을 기수 정렬을 사용하여 오름차순으로 정렬하시오.
입력: [170, 45, 75, 90, 802, 24, 2, 66]
출력: [2, 24, 45, 66, 75, 90, 170, 802]

문제 풀이 과정

가장 낮은 자릿수부터 시작합니다. 첫 번째 자릿수인 1의 자리 숫자로 정렬합니다.

C#
public static void LSDRadixSort(int[] array)
{
    // 가장 큰 숫자를 찾습니다.
    int max = array.Max();
    // 자릿수를 찾습니다.
    for (int exp = 1; max / exp > 0; exp *= 10)
    {
        CountingSort(array, exp);
    }
}

private static void CountingSort(int[] array, int exp)
{
    int n = array.Length;
    int[] output = new int[n]; // 정렬된 배열
    int[] count = new int[10]; // 0-9까지의 숫자 카운트

    // 자릿수에 해당하는 원소 개수를 계산합니다.
    for (int i = 0; i < n; i++)
    {
        count[(array[i] / exp) % 10]++;
    }

    // 누적 카운트를 계산합니다.
    for (int i = 1; i < 10; i++)
    {
        count[i] += count[i - 1];
    }

    // 정렬된 배열을 만듭니다.
    for (int i = n - 1; i >= 0; i--)
    {
        output[count[(array[i] / exp) % 10] - 1] = array[i];
        count[(array[i] / exp) % 10]--;
    }

    // 원본 배열을 업데이트합니다.
    for (int i = 0; i < n; i++)
    {
        array[i] = output[i];
    }
}

위의 코드에서 우리는 LSDRadixSort 메서드를 정의하였습니다. 이 메서드는 각 자릿수에 대해 CountingSort 도움을 받아 정렬을 진행합니다.

5. 구현 및 실행

이제 위의 함수를 사용하여 전체 프로그램을 실행해보겠습니다. 아래는 프로그램의 전체 코드입니다:

C#
using System;
using System.Linq;

class Program
{
    public static void Main(string[] args)
    {
        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
        LSDRadixSort(array);

        Console.WriteLine("정렬된 배열:");
        Console.WriteLine(string.Join(", ", array));
    }
  
    public static void LSDRadixSort(int[] array)
    {
        int max = array.Max();
        for (int exp = 1; max / exp > 0; exp *= 10)
        {
            CountingSort(array, exp);
        }
    }

    private static void CountingSort(int[] array, int exp)
    {
        int n = array.Length;
        int[] output = new int[n];
        int[] count = new int[10];

        for (int i = 0; i < n; i++)
        {
            count[(array[i] / exp) % 10]++;
        }

        for (int i = 1; i < 10; i++)
        {
            count[i] += count[i - 1];
        }

        for (int i = n - 1; i >= 0; i--)
        {
            output[count[(array[i] / exp) % 10] - 1] = array[i];
            count[(array[i] / exp) % 10]--;
        }

        for (int i = 0; i < n; i++)
        {
            array[i] = output[i];
        }
    }
}

위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다:


정렬된 배열:
2, 24, 45, 66, 75, 90, 170, 802

6. 기수 정렬의 장단점

기수 정렬의 장점은 다음과 같습니다:

빠른 속도: 특정 조건에서 우수한 성능을 보입니다. (즉, 범위가 제한적일 때)
안정적 정렬: 동일한 값에 대한 상대적인 순서 유지.

그러나 단점도 존재합니다:

메모리 사용: 추가적인 메모리가 필요합니다.
제한된 데이터: 정수가 아닌 다른 자료형에 대해서는 사용이 어렵습니다.

7. 마무리

오늘은 기수 정렬의 기본 개념, 동작 원리, 시간 복잡도, 문제 예제에 대한 풀이 등을 살펴보았습니다. 이 알고리즘은 정수가 포함된 컬렉션을 효율적으로 처리하는 데 매우 유용합니다. 실제 코딩 테스트에서도 기수 정렬을 사용해보면 좋습니다.

그럼 다음 강좌에서 또 만나요! 각자 코딩 테스트 준비 잘 하세요!