카운팅정렬이라는 생소한 이름의 정렬 방식을 봐서 무슨 방식인지 알아보았다.
카운팅정렬이란?
다른 원소들끼리 비교를 하지 않고서도 크기대로 정렬할 수 있으며, 숫자의 범위가 작을수록 훨씬 빠르다.
정렬 과정
0. 예시
1. 원소에 있는 숫자들이 총 몇번씩 등장하는지 센다.
2. n번째 칸에 있는 숫자를 n + (n-1 번째 수)로 바꾼다. (피보나치 수열과 약간 비슷)
여기서 숫자의 의미를 잠깐 살펴보고 가야할 필요가 있다.
예를들어 3에는 4이라는 숫자가 기록되어 있는데, 여기에 있는 4는 원래 2에 들어있던 숫자 3과 원래 4에 들어 있던 숫자 1의 합이다. 즉, 3까지의 숫자 합 + 4가 등장한 개수 = 1~4까지의 총 등장 횟수가 4에 저장되는 것이다.
마찬가지로 n번째 칸에는 1~n-1까지의 숫자 등장 횟수 + n이 등장한 횟수가 저장되어 있으므로, n에는 1~n까지의 총 등장 횟수가 저장되어 있다는 것을 일반화시킬 수 있다.
3. 칸에 적혀있는 위치에 해당 숫자를 배치한다. 배치한 후에는 표에있는 값에서 1을 뺀다.
숫자를 배열할 경우를 생각해보자. 낮은숫자부터 높은숫자까지를 배열한다고 하면, 만약 1~n까지의 숫자가 등장한 횟수가 N이라고 한다면, 숫자 n이 배치되는 가장 마지막 위치는 N일 것이다.
따라서 만약 배열에 n이 있다면 N번째 자리에 배치하고 다시 한번 등장한다면 한칸씩 앞으로 배치하면 될것이다.
이로써 비교 과정 "없이" 오름차순 배열이 완료되었다.
C언어로 구현해보자
1. 원소에 있는 숫자들이 총 몇번씩 등장하는지 센다.
표에 기록할 범위를 알아내기 위해 배열에 등장하는 숫자의 최대값과 최소값을 알아내야 한다.
int minn(int* arr, int len) {
int flag = 0;
int min = 0;
for (int* i = arr; i < arr + len; i++) {
if (flag == 0 || min > *(i)) {
flag = 1;
min = *i;
}
}
return min;
}
int maxx(int* arr, int len) {
int flag = 0;
int max = 0;
for (int* i = arr; i < arr + len; i++) {
if (flag == 0 || max < *(i)) {
flag = 1;
max = *i;
}
}
return max;
}여기에서 구한 최대, 최솟값을 이용해서 범위를 정한 후 각 숫자가 몇번 등장하는지 기록한다.
void count_number(int* table, int* arr, int len, int min, int max){
for (int* i = arr; i < arr + len; i++) {
table[(*i - min)]+=1;
}
}
2. n번째 칸에 있는 숫자를 n + (n-1 번째 수)로 바꾼다. (피보나치 수열과 약간 비슷)
void accum(int* arr, int range) {
if (range >= 2) {
for (int i = 1; i < range; i++) {
*(arr + i) = *(arr + i - 1) + *(arr + i);
}
}
}3. 칸에 적혀있는 위치에 해당 숫자를 배치한다. 배치한 후에는 표에있는 값에서 1을 뺀다.
void append(int* arr,int* result, int* table,int min, int index) {
result[table[arr[index] - min] - 1] = arr[index];
table[arr[index] - min]--;
}
<전체 코드>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int minn(int* arr, int len) {
int flag = 0;
int min = 0;
for (int* i = arr; i < arr + len; i++) {
if (flag == 0 || min > *(i)) {
flag = 1;
min = *i;
}
}
return min;
}
int maxx(int* arr, int len) {
int flag = 0;
int max = 0;
for (int* i = arr; i < arr + len; i++) {
if (flag == 0 || max < *(i)) {
flag = 1;
max = *i;
}
}
return max;
}
void count_number(int* table, int* arr, int len, int min, int max){
for (int* i = arr; i < arr + len; i++) {
table[(*i - min)]+=1;
}
}
void accum(int* arr, int range) {
if (range >= 2) {
for (int i = 1; i < range; i++) {
*(arr + i) = *(arr + i - 1) + *(arr + i);
}
}
}
void append(int* arr,int* result, int* table,int min, int index) {
result[table[arr[index] - min] - 1] = arr[index];
table[arr[index] - min]--;
}
int main() {
int* nums;
int n;
scanf("%d", &n);
nums = (int*)malloc(sizeof(int) * n);
int* result = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
scanf("%d", nums + i);
}
int ma = maxx(nums, n);
int mi = minn(nums, n);
int* table = (int*) calloc(( ma-mi + 1),sizeof(int) );
count_number(table, nums, n, mi, ma);
accum(table, ma-mi+1);
int table_index = 0;
for (int i = 0; i < n; i++) {
append(nums, result, table, mi, i);
}
for (int i = 0; i < n; i++) {
printf("%d\n", *(result + i));
}
}
적용해보자
문제의 힌트에 카운팅정렬을 이용해서 오름차순으로 정렬해 보라고 나와있었다.
하지만 위의 코드를 그대로 사용하면 문제에서 제시되어있는 메모리 제한을 초과해버리게 된다.
nums = (int*)malloc(sizeof(int) * n);
int* result = (int*)malloc(sizeof(int) * n);
int* table = (int*) calloc(( ma-mi + 1),sizeof(int) );
메모리 초과가 발생하는 원인이다. N의 범위를 보면 1천만까지라고 되어있다. 정렬해야할 배열의 길이가 최대 1천만이라는것인데, 필요한 메모리 용량을 계산해보면 nums 배열 하나만 하더라도 40메가바이트 이상이 필요하게 된다.(4바이트 * 1천만)
따라서 정렬 대상 배열을 저장하는 방법으로 풀 수는 없다.
그럼 어떻게 풀어야 하느냐? N 이후 입력되는 수들의 범위를 보면 1만 이하라고 나와있다.
따라서 2번 과정에 나와있는 표의 범위를 1~10000으로 미리 설정해놓은 다음 사용자로부터 입력을 받는 순간 바로 표에 반영하는 방향으로 가야 한다.
int* table = (int*) calloc((10001),sizeof(int) );
for (int i = 0; i < n; i++) {
int tmp;
scanf("%d", &tmp);
table[tmp] += 1;
}그리고 입력이 끝난 이후에는 표에 나타나 있는 누적합을 이용해서 따로 result 배열에 담지 않고 오름차순으로 출력한다.
int table_index = 0;
for (int i = 0; i < n && table_index <= 10000; i++) {
while(i >= table[table_index]) {
table_index++;
}
if (i < table[table_index]) {
printf("%d\n", table_index);
}
}
전체 코드는 다음과 같다. 최대최소 값을 구하는것이 의미가 없어졌기 때문에 main 함수에서도 수정이 조금씩 이루어졌다.
#include <stdio.h>
#include <stdlib.h>
int minn(int* arr, int len) {
int flag = 0;
int min = 0;
for (int* i = arr; i < arr + len; i++) {
if (flag == 0 || min > *(i)) {
flag = 1;
min = *i;
}
}
return min;
}
int maxx(int* arr, int len) {
int flag = 0;
int max = 0;
for (int* i = arr; i < arr + len; i++) {
if (flag == 0 || max < *(i)) {
flag = 1;
max = *i;
}
}
return max;
}
void count_number(int* table, int* arr, int len, int min, int max){
for (int* i = arr; i < arr + len; i++) {
table[(*i - min)]+=1;
}
}
void accum(int* arr, int range) {
if (range >= 2) {
for (int i = 1; i < range; i++) {
*(arr + i) = *(arr + i - 1) + *(arr + i);
}
}
}
void append(int* arr,int* result, int* table,int min, int index) {
result[table[arr[index] - min] - 1] = arr[index];
table[arr[index] - min]--;
}
int main() {
int* nums;
int n;
scanf("%d", &n);
int* table = (int*) calloc((10001),sizeof(int) );
for (int i = 0; i < n; i++) {
int tmp;
scanf("%d", &tmp);
table[tmp] += 1;
}
accum(table, 10001);
for (int i = 0; i < 5; i++) {
}
int table_index = 0;
for (int i = 0; i < n && table_index <= 10000; i++) {
while(i >= table[table_index]) {
table_index++;
}
if (i < table[table_index]) {
printf("%d\n", table_index);
}
}
}비록 정렬된 배열을 저장할 수는 없지만, 메모리를 엄청 많이 절약하였고, 출력만은 온전하게 이루어지기 때문에 문제를 해결할 수 있다.
'알고리즘' 카테고리의 다른 글
| 모든 순열 구하기 (0) | 2022.03.06 |
|---|---|
| [C언어] 병합정렬 구현하기 (feat. 백준 2751번) (0) | 2022.02.21 |
