자바스크립트 코딩테스트 강좌, 기수 정렬

본 강좌에서는 자바스크립트로 구현된 기수 정렬(Radix Sort) 알고리즘을 소개하고, 이를 어떻게 활용하여 코딩테스트 문제를 해결할 수 있는지에 대해 상세히 설명하겠습니다. 기수 정렬 알고리즘의 개념, 구현 방법, 시간 복잡도, 예제 문제를 통해 체계적으로 학습해보겠습니다.

기수 정렬(Radix Sort)란?

기수 정렬은 정렬 알고리즘 중 하나로, 비슷한 수의 자릿수(digit)를 가지는 수들을 정렬할 때 효율적인 방법입니다. 이 방법의 핵심은 숫자를 개별 자리(1의 자리, 10의 자리 등)로 나누어 정렬한 후, 자릿수를 순차적으로 고려하여 전체 숫자를 정렬하는 방식입니다.

기수 정렬의 원리

기수 정렬은 다음과 같은 순서로 진행됩니다:

입력된 배열의 최대 자릿수를 찾습니다. 이는 정렬을 수행할 때 몇 번의 패스(pass)가 필요한지를 결정합니다.
각 자릿수에 대해 안정 정렬을 수행합니다. 가장 낮은 자리(1의 자리)부터 시작하여 가장 높은 자리(최대 자릿수)까지 반복합니다.
최종적으로 모든 자릿수에 대한 정렬이 완료된 후, 원본 배열은 정렬된 상태가 됩니다.

시간 복잡도

기수 정렬의 시간 복잡도는 주로 사용하는 안정 정렬 알고리즘에 따라 다르지만, 일반적으로 O(nk)입니다. 여기서 n은 정렬할 숫자의 개수, k는 가장 큰 숫자의 자릿수입니다. 기수 정렬은 특성상 정수에 대해서만 사용될 수 있지만, 문자나 문자열에 대해서도 변형된 버전으로 적용할 수 있습니다.

자바스크립트로 기수 정렬 구현하기

기본 알고리즘 구현

아래는 자바스크립트로 구현된 기수 정렬의 예시 코드입니다:

function getMax(array) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

function countingSort(array, place) {
    const n = array.length;
    const output = new Array(n);
    const count = new Array(10).fill(0);

    for (let i = 0; i < n; i++) {
        const digit = Math.floor(array[i] / place) % 10;
        count[digit]++;
    }

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

    for (let i = n - 1; i >= 0; i--) {
        const digit = Math.floor(array[i] / place) % 10;
        output[count[digit] - 1] = array[i];
        count[digit]--;
    }

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

function radixSort(array) {
    const max = getMax(array);
    for (let place = 1; Math.floor(max / place) > 0; place *= 10) {
        countingSort(array, place);
    }
    return array;
}

// 사용 예시
const numbers = [170, 45, 75, 90, 802, 24, 2, 66];
console.log(radixSort(numbers)); // 출력: [2, 24, 45, 66, 75, 90, 170, 802]

문제 예시: 정수 배열 정렬

자, 이제 기수 정렬을 실제 문제에 적용해 보겠습니다. 문제는 다음과 같습니다:

문제: 정수 배열이 주어질 때, 기수 정렬 알고리즘을 이용하여 이 배열을 오름차순으로 정렬하는 함수를 작성하시오.

문제 접근 방식

입력 배열을 함수의 인자로 받아옵니다.
기수 정렬 알고리즘을 활용하여 배열을 정렬합니다.
정렬된 배열을 반환합니다.

구현 및 테스트

위에서 설명한 기수 정렬 알고리즘을 바탕으로 위 문제를 해결하기 위한 함수를 아래와 같이 구현할 수 있습니다:

function sortIntegers(array) {
    return radixSort(array);
}

// 테스트
const testArray = [5, 3, 8, 1, 2, 7, 4, 6];
console.log(sortIntegers(testArray)); // 출력: [1, 2, 3, 4, 5, 6, 7, 8]

결론

이번 강좌에서는 기수 정렬 알고리즘에 대해 알아보고, 자바스크립트로 어떻게 구현하는지 살펴보았습니다. 기수 정렬은 대량의 정수를 정렬할 때 매우 효율적이며, 특히 자릿수가 적은 수에 대해서 뛰어난 성능을 보여줍니다. 다양한 코딩테스트 문제를 접근하기 위해 기수 정렬을 활용해보는 것은 매우 유익한 경험이 될 것입니다. 앞으로의 코딩테스트에서 기수 정렬의 개념과 구현 방법을 잘 활용하시기 바랍니다.