문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
정말 간단한 정렬 문제처럼 보인다. 하지만, 문제에는 특수한 메모리 제한과 시간 제한이 존재한다. 시간 제한은 큰 문제가 되지 않았지만, 메모리 제한이 크게 발목을 잡았다.
우선 맨 처음 생각나는 방법은, 당연히 qsort 내장 함수를 이용하는 것이다. 당연히, 이 제출은 메모리 제한에 걸리게 되었고, 이를 해결하기 위해 새로운 정렬을 찾게 되었다.
이 문제에서 우리에게 요구하는 것은 카운팅 정렬 (Counting Sort)이다.
카운팅 정렬 (Counting Sort)이란?
각 원소가 얼마나 많은 빈도로 나오고 있는지에 대한 정보를 저장한 후, 이에 맞춰 정렬해주는 기법이라고 한다.
처음 설명을 들어서는 무슨 소리인지 하나도 모르겠다. 필자도 처음엔 무슨 소리인지 몰랐다. 천천히 짚어보겠다.
1번째
우선, 정렬할 배열을 하나 설정하겠다.
정렬할 배열 : { 1, 6, 9, 3, 6, 1, 5, 7, 2 }
정렬된 배열 : { 1, 1, 2, 3, 5, 6, 6, 7, 9 }
이 배열을 기반으로, 각 원소가 얼마나 많은 빈도로 나오는지 저장하는, 완전히 새로운 배열을 하나 더 만든다. 정렬할 배열의 원소를 Index로 하는 위치에 1을 더해주는 느낌이다. 배열의 크기는, 현재 정렬할 배열에서 가장 큰 원소 + 1이다.
새로운 배열 : { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
// 정렬할 배열에서 가장 큰 원소 = 9
// 9 + 1 = 10 크기의 배열을 생성
위 배열에서, 맨 처음 나오는 원소는 1이다. 1을 Index로 가지는 위치에 1을 더해주면
새로운 배열 : { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0 }
이 될 것이다. 다음 원소인 6을 만나면, 6을 Index로 가지는 위치에 1을 더해준다.
새로운 배열 : { 0, 1, 0, 0, 0, 0, 1, 0, 0, 0 }
이런 과정을 반복하면, 밑과 같은 모양의 배열이 나오게 된다.
새로운 배열 : { 0, 2, 1, 1, 0, 1, 2, 1, 0, 1 }
우린 이렇게 2개의 배열을 얻게 되었다.
정렬할 배열 : { 1, 6, 9, 3, 6, 1, 5, 7, 2 }
빈도 배열 : { 0, 2, 1, 1, 0, 1, 2, 1, 0, 1 }
2번째
그 다음, 빈도 배열을 누적합으로 변환시킨다. 즉, 앞 원소와 자신을 더한 원소를 저장하게 바꾼다.
예를 들어, 빈도 배열의 첫 번째 원소는 0, 두 번째 원소는 2이다.
그래서 두 번째 원소는 첫 번째 원소 0과 자기 자신(0)을 더해서 2가 된다.
세 번째 원소는, 두 번째 원소인 2와 자기 자신(1)을 더해서 3이 된다.
네 번째 원소는, 세 번째 원소인 3과 자기 자신(1)을 더해서 4가 된다.
...
이런 식으로 계산하게 되면, 빈도 배열은 다음과 같이 바뀌게 된다.
빈도 배열 : { 0, 2, 3, 4, 4, 5, 7, 8, 8, 9 }
바뀐 배열과 우리가 정렬을 끝마쳤을 때의 배열을 비교해보도록 하자.
빈도 배열 : { 0, 2, 3, 4, 4, 5, 7, 8, 8, 9 }
정렬된 배열 : { 1, 1, 2, 3, 5, 6, 6, 7, 9 }
둘은 특정한 관계에 놓여있다. 바로 빈도 배열이 가지는 값은 정렬된 배열의 경계선을 알려준다는 것이다.
정렬된 배열의 1, 2번째 원소 = 1, 1에 해당하는 Index를 빈도 배열에 적용시키면 나오는 원소 = 2
정렬된 배열의 3번째 원소 = 2, 2에 해당하는 Index를 빈도 배열에 적용시키면 나오는 원소 = 3
...
이와 같은 규칙성을 가지고 있다.
정렬할 배열 : { 1, 6, 9, 3, 6, 1, 5, 7, 2 }
빈도 배열 : { 0, 2, 3, 4, 4, 5, 7, 8, 8, 9 }
3번째
정렬할 배열에서 원소를 하나씩 가지고 와서, 빈도 배열의 Index로 사용한다. 배열의 Index는 0부터 시작하므로, Index로 사용한 후 나온 원소를 배열에 넣기 전 1을 빼준다. 주의할 점은, 앞에서부터 작업을 시행해도 정렬이 되는건 맞지만, 안정 정렬(Stable Sort)을 지키기 위해서는 뒤에서부터 정렬하는 것이 옳다.
정렬할 배열 : { 1, 6, 9, 3, 6, 1, 5, 7, 2 }
빈도 배열 : { 0, 2, 3, 4, 4, 5, 7, 8, 8, 9 }
정렬할 배열의 마지막 원소 = 2
빈도 배열의 Index 2에 들어가 있는 원소 = 3, 배열의 특성상 1을 빼주면 2가 된다.
결과 배열 : { 0, 0, 2, 0, 0, 0, 0, 0, 0 }
다음 원소 = 7
빈도 배열의 Index 7에 들어가 있는 원소 = 8, 배열의 특성상 1을 빼주면 7이 된다.
결과 배열 : { 0, 0, 2, 0, 0, 0, 7, 0, 0 }
다음 원소 = 5
빈도 배열의 Index 5에 들어가 있는 원소 = 5, 배열의 특성상 1을 빼주면 4가 된다.
결과 배열 : { 0, 0, 2, 0, 5, 0, 7, 0, 0 }
다음 원소 = 1
빈도 배열의 Index 1에 들어가 있는 원소 = 2, 배열의 특성상 1을 빼주면 1이 된다.
결과 배열 : { 0, 1, 2, 0, 5, 0, 7, 0, 0 }
정렬 과정에 들어가 있는 1은 총 2개이고, 현재 검사하는 1은 그 2개 중 2번째 1이다.
정렬이 완료된 배열과 비교해보면, 안정 정렬을 지키며 들어갔다는 것을 알 수 있다.
위 과정을 맨 앞 원소까지 반복하면, 정렬이 완료되게 된다.
카운팅 정렬은 시간복잡도로 보았을 때, O(n)이라는 미친 성능을 가지고 있다. 하지만, 이런 성능과는 비례하여 제한된 상황에서밖에 사용하지 못한다.
- 데이터의 크기 범위가 제한되었을 때
- 데이터가 양의 정수일 경우 (양의 실수일 경우, 실수는 기본적으로 무한이기 때문에 1번 조건이 만족되지 못한다)
위와 같은 조건에서는 사용하면, 메모리를 많이 먹게 된다고 한다.
극단적인 예로, 정렬할 배열의 크기는 크지 않지만, 만약 원소 중 하나가 1,000,000,000을 넘는다고 치자. 그렇다면, 맨 처음 빈도 배열을 만들 때의 조건을 다시 떠올려보자.
배열의 크기는, 현재 정렬할 배열에서 가장 큰 원소 + 1이다.
그렇기 때문에, 빈도 배열을 만들 때 엄청 큰 크기의 배열을 만들어야 하는 문제가 생긴다.
여기까지가 카운팅 정렬의 정리이다. 그래서 위 정렬을 사용하면 코드가 맞느냐?
정말 아쉽게도, 위의 정렬 방식을 따르게 되면 전부 메모리 초과가 나오게 되었다.
카운팅 정렬에서 사용하는 배열은 총 3개(정렬할 배열, 빈도 배열, 정렬된 배열)이다. 처음엔 이 셋을 모두 동적 할당으로 배열을 부여해주었고, 동적 할당이 틀리다고 생각해서 문제에서 나온 범위대로 배열을 많이 크게 만들어서 해결하려고 했지만, 모두 메모리 초과가 일어난 모습을 볼 수 있다.
기본적으로 배열을 사용하게 되면, 메모리를 많이 먹을 수 밖에 없다. 그래서, 배열을 줄이는 방법을 고민하다가 새로운 생각이 떠올라 코드를 작성했고, 맨 위의 코드가 바로 그것이다.
조금 눈치 빠른 사람들은 느꼈을지도 모르겠지만, 그저 정렬을 하기 위함이라면 우리가 정말로 필요한 배열은 사실 누적합을 진행하지 않은 빈도 배열밖에 없을 것이다. 위 빈도 배열을 잠시 가져오겠다.
빈도 배열 : { 0, 2, 1, 1, 0, 1, 2, 1, 0, 1 }
Index 값이 1이고, 그 안의 원소가 2라면,
정렬할 배열에서 원소 1이 총 2개 있다
라는 뜻이다. 그럼, 빈도 배열의 Index가 원소가 되고, 빈도 배열의 원소가 총 개수가 되는 것이다.
위 빈도 배열로 정렬하게 된다면,
정렬된 배열 : { 1, 1, 2, 3, 5, 6, 6, 7, 9 }
1 2개, 2 1개, 3 1개, 5 1개, 6 2개, 7 1개, 9 1개
를 빈도 배열과 비교해보자.
이렇게 된다면, 배열을 하나만 사용해서도 문제를 풀 수 있을 것이다.
#include <stdio.h>
int main(void)
{
int arr[10001] = { 0 };
int testcase;
scanf("%d", &testcase);
int temp;
for (int i = 0; i < testcase; i++)
{
scanf(" %d", &temp);
arr[temp]++;
}
for (int i = 0; i < 10001; i++)
{
if (arr[i] != 0)
{
for (int j = 0; j < arr[i]; j++)
{
printf("%d ", i);
}
}
}
return 0;
}답안으로 제출한 코드는 위와 같고,
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int arr_size;
scanf("%d", &arr_size);
int* arr = (int*)malloc(sizeof(int) * arr_size);
int* result = (int*)malloc(sizeof(int) * arr_size);
for (int i = 0; i < arr_size; i++)
{
scanf(" %d", &arr[i]);
}
int max = -1;
for (int i = 0; i < arr_size; i++)
{
if (max < arr[i])
{
max = arr[i];
}
}
printf("%d\n", max);
int* counting = (int*)calloc(max + 1, sizeof(int));
for (int i = 0; i < arr_size; i++)
{
counting[arr[i]]++;
}
for (int i = 1; i < max + 1; i++)
{
counting[i] += counting[i - 1];
}
for (int i = 0; i < arr_size; i++)
{
counting[arr[i]]--;
result[counting[arr[i]]] = arr[i];
}
for (int i = 0; i < arr_size; i++)
{
printf("%d ", result[i]);
}
free(result);
free(counting);
free(arr);
return 0;
}카운팅 정렬을 이용해서 제출한 코드는 다음과 같다.
제출한 코드는 메모리를 덜 사용하는 대신, 시간이 조금 오래 걸리는 2중 반복문을 사용했다. 하지만, 카운팅 솔트는 반복문의 양 자체는 많지만, 중첩된 반복문은 존재하지 않기 때문에 시간이 조금 덜 걸릴 것이다.
