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

1. 기수 정렬(Radix Sort) 개요

기수 정렬은 특수한 형태의 정렬 알고리즘으로, 정렬할 데이터가 특정한 범위 내의 정수나 문자열일 때 효과적입니다. 일반적인 정렬 알고리즘과는 달리 기수 정렬은 “자릿수”를 기준으로 정렬을 수행합니다. 이를 통해 기수 정렬은 O(d(n + k))의 시간 복잡도를 가집니다. 여기서 d는 자릿수의 수, n은 정렬할 데이터의 수, k는 특정한 범위의 값입니다.

2. 기수 정렬의 원리

기수 정렬은 다음과 같은 과정을 통해 이루어집니다:

1. 가장 낮은 자릿수부터 시작하여, 각 자릿수를 기준으로 숫자를 정렬합니다.
2. 각 자릿수에 대해 정렬을 반복합니다.
3. 모든 자릿수에 대해 정렬을 완료하면 최종적으로 정렬된 배열을 얻게 됩니다.

기수 정렬은 보통 안정적인 정렬 알고리즘으로 구현됩니다. 즉, 같은 값의 원소 순서는 서로의 상대적인 위치를 유지합니다.

3. 기수 정렬 구현

기수 정렬을 C++로 구현해 보겠습니다. 다음은 기수 정렬의 기본 구현입니다:

#include <iostream>
#include <vector>

using namespace std;

// 특정 자릿수에서의 정렬을 위한 함수
void countingSort(vector<int> &arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0}; // 숫자의 범위가 0~9

    // 각 자릿수의 수를 카운트
    for (int i = 0; i < n; i++) {
        count[(arr[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[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // 결과를 원래 배열에 저장
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
}

// 기수 정렬 함수
void radixSort(vector<int> &arr) {
    // 최대값을 찾기
    int maxVal = *max_element(arr.begin(), arr.end());

    // 자릿수 별로 정렬
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSort(arr, exp);
    }
}

// 메인 함수
int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    
    cout << "정렬된 배열: ";
    for (int i : arr) {
        cout << i << " ";
    }
    
    return 0;
}
        

이 코드는 기수 정렬의 기본적인 흐름을 보여줍니다. countingSort 함수는 각 자릿수에 대해 개수를 세고, 이를 바탕으로 원소들을 정렬합니다. radixSort 함수는 모든 자릿수에 대해 countingSort 함수를 호출하여 최종적으로 정렬된 배열을 반환합니다.

4. 기수 정렬로 풀 수 있는 예제 문제

이번에는 기수 정렬을 이용하여 해결할 수 있는 알고리즘 문제를 소개하겠습니다.

문제: 주어진 정수 리스트를 기수 정렬을 통해 정렬하라.

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

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

문제 풀이 과정

1. 최대값을 찾아서 802임을 확인합니다. 이 값을 통해 가장 높은 자릿수를 결정합니다.
2. 1의 자릿수부터 시작하여 각 자릿수에 대해 countingSort를 호출합니다. 1의 자릿수, 10의 자릿수, 100의 자릿수 순서로 호출합니다.
3. 각 자릿수에 대해 정렬 수행 후, 최종 배열이 정렬됩니다.

기수 정렬을 적용하여 문제를 해결해 보세요!