Back to Blog
알고리즘정렬CountingSortRadixSortSTL sort

0x0F. 정렬 알고리즘 II - 병합, 퀵, 카운팅 정렬

Counting Sort, Radix Sort, STL Sort 사용법과 비교함수 작성법을 정리한다.

0x0F 정렬 II

0x00 Counting Sort

Counting Sort 원리

각 수의 등장 횟수만 카운팅해서 횟수만큼 출력하는 알고리즘. 정렬 알고리즘 중에서 가장 쉬운 알고리즘이다.

이론적으로는 수의 범위가 0에서 1억까지여도 카운팅 소트를 쓸 수 있지만 풀이를 하는 입장에서는 수의 범위가 대략 1000만 이하일때에는 카운팅 소트를 쓰고 그렇지 않을 경우에는 카운팅 소트를 쓰지 못한다고 생각하면 된다.

BOJ 15688번 : 수 정렬하기 5

#include <bits/stdc++.h>
using namespace std;

int freq[2000001]
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  while(n--) {
  	int a;
    cin >> a;
    freq[1000000+a]++;
  }
  for (int i = 0; i < 2000001; i++)
    while (freq[i]--) cout << i-1000000 << '\n';
}

시간복잡도는 수의 범위가 K개라고 할 때 맨 처음 N개의 수를 보면서 freq 배열에 값을 추가하고 답을 출력할 때, 혹은 정렬을 수행할 때 총 K칸의 값을 확인해야 하기 때문에 O(N+K).

수의 범위 K가 제한되어 있을 때에는 카운팅 소트를 쓰면 굉장히 구현이 간단해서 활용할 여지가 있다, 그렇지만 수의 범위가 크면 카운팅 소트를 사용할 수 없다.

0x01 Radix Sort

Radix Sort 원리

각 자리수에 대해 카운팅 소트 실행

#include <bits/stdc++.h>
using namespace std;

int n = 15;
int arr[1000001] = {...};
int d = 3;
int p10[3];

int digitNum(int x, int a) [
	return (x / p10[a]) % 10;
}

vector<int> v[10];
int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    // pow 함수를 써서 p10[i] = pow(10, i); 와 같은 방식으로 하면
    // pow는 실수형을 반환하는 함수이기 때문에 실수 오차로 인해 꼬여버릴 수 있다
    p10[0] = 1;
    for(int i=1; i<d; i++) p10[i]= p10[i-1] * 10;
    for(int i=0; i<d; i++) {
    	for(int j=0; j<10; j++) v[i].clear();
        for(int j=0; j<n; j++)
        	v[digitNum(arr[j], i)].push_back(arr[j]);
        int idx= 0;
        for(int j=0; j<10; j++)
        	for(auto x : v[j]) arr[idx++]= x;
    }
    for(int i=0; i<n; i++) cout << arr[i] << " ";
}

시간복잡도는 자릿수의 최대 개수가 D개라고 할 때 D번에 걸쳐서 카운팅 소트를 하는 것과 상황이 똑같다. 그러면 리스트의 개수를 K개라고 할 때 엄밀하게 말하면 시간복잡도는 O(D(N+K))이지만 보통 리스트의 개수는 N에 비해 무시가 가능할 정도로 작다. 결론적으로 라딕스 소트의 시간복잡도는 O(DN).

실제 구현을 할 때 C++의 배열을 이용하면 N개의 원소를 정렬할 때 한 리스트에 N개의 원소가 다 몰릴 수도 있으니 10개의 리스트 모두를 N칸의 배열로 만들어야 하는데 이건 너무 공간의 낭비가 심하다. 공간의 낭비를 해결하려면 각 리스트를 vector와 같은 동적 배열 혹은 연결 리스트로 사용해야 하는데 STL이 없으면 구현이 많이 까다롭고, STL을 쓸 수 있는 상황이라면 그냥 STL sort 함수를 쓰는게 낫다.

그렇기 때문에 코딩테스트에서 머지 소트나 기타 다른 소트를 구현할 일도 STL을 쓸 수 없는 아주 드문 환경 이외에는 없지만, 특히 라딕스 소트는 구현을 해야하는 상황이 아예 없다.

Comparison Sort 머지, 퀵, 버블 소트는 원소들끼리 크기를 비교하는 과정이 있었는데 카운팅, 라딕스 소트는 원소들간의 크기를 비교 하지 않고 정렬을 수행한다. 그래서 버블, 머지, 퀵 소트는 Comparison Sort인 반면 카운팅, 라딕스 소트는 Non-comparison Sort.

0x02 STL Sort

다만 sort 함수는 stable sort가 아니다. 그래서 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않을 수 있다. 꼭 stable sort가 필요하다면 stable_sort 함수를 사용. stable_sort 또한 sort 함수와 사용법이 똑같다.

또한 pair, tuple에는 이미 대소 관계가 우리에게 익숙한대로 먼저 제일 앞의 원소의 대소를 비교하고, 값이 같으면 그 다음 원소의 대소를 비교하는 방식으로 정해져있다.

예를 들어 pair에서 5 < -2, tuple에서 0 > 6.

그래서 좌표를 정렬하거나 기타 여러 속성이 있는 원소를 정렬할 때 별도로 구조체를 둘 필요가 없고 pair나 tuple 등을 이용하면 된다.

비교 함수

int형을 5로 나눈 나머지 순으로, 5로 나눈 나머지가 같다면 크기 순으로 정렬하고 싶으면 비교 함수를 만들어서 인자로 주면 된다.

Result : 5, 1, 6, 2, 7, 3, 4.

이처럼 비교 함수 cmp(int a, int b)는 a가 b의 앞에 와야할 때 true를, 그렇지 않을 때에는 false를 반환해야 한다.

주의사항

  1. a가 b의 앞에 와야할 때만 true를 반환해야 하니 두 값이 같을 때 혹은 우선순위가 같을 때에는 반드시 false를 반환.
  2. 함수의 인자로 STL이나 구조체 객체를 실어서 보내면 값의 복사가 일어나는데 굳이 복사라는 불필요한 연산을 추가로 하면서 시간을 잡아먹을 필요가 없다. 따라서 복사를 하는 대신 reference를 보내기.
reference 사용

const string& a, const string& b라고 쓰면 이 cmp 함수에서 a와 b의 값은 변하지 않는다는걸 명시적으로 나타내기 때문에 제대로 된 코딩을 할 때에는 const라는걸 달아주는게 좋은데 사실 코딩테스트에서는 그냥 const를 쓰지 않아도 크게 상관은 없다.

BOJ 1431번 : 시리얼 번호

#include <bits/stdc++.h>
using namespace std;

int n;
string arr[52];

bool cmp(const string &a, const string &b) {
  // 1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
  if (a.size() != b.size())
    return a.size() < b.size();
  // 2. 숫자인 것만 더해서 작은 것이 먼저 온다.
  else {
    int acount= 0, bcount= 0;
    for (int i= 0; i < a.size(); i++)
      if (a[i] > '0' && a[i] <= '9')
        acount = a[i] - '0';
    for (int i= 0; i < b.size(); i++)
      if (b[i] > '0' && b[i] <= '9')
        bcount = b[i] - '0';
    if (acount = bcount)
      return acount < bcount;
  }
  // 3. 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.
  return a < b;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  sort(arr, arr+n, cmp);
  for(int i=0; i<n; i++)
    cout << arr[i] << "\n";
}

비교 함수 cmp를 사용해서 연습

0x03 정렬의 응용

BOJ 11652번 : 카드

#include <bits/stdc++.h>
using namespace std;

int n;
long long arr[100002];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  sort(arr, arr + n);

  int cnt = 0;
  long long mxval = -(1ll << 62) -1;
  int mxcnt= 0;
  for (int i= 0; i < n; i++) {
    if (i= 0 || arr[i-1]= arr[i]) cnt++;
    else {
      if (mxcnt < cnt) {
        mxcnt= cnt;
        mxval= arr[i - 1];
      }
      cnt= 1;
    }
  }
  if(cnt > mxcnt) mxval = arr[n-1];
  cout << mxval << "\n";
}
  • 수의 범위가 int 안에는 다 담기지 않고 long long을 써야한다는 점에 주의!
  • 제일 마지막 수에 대한 처리가 있어야 한다는건 유의
  • a[n]에 2^62 + 1 값을 넣고 for문을 n-1까지가 아니라 n까지 돌면 마지막 줄을 지울 수 있고, 또 cnt에 0을 넣는게 아니라 1을 넣고 시작하면 i를 0이 아닌 1부터 시작해버릴 수 있어서 i == 0일 때를 별도로 예외처리할 필요가 없어진다.

문제 풀이

정렬에 해당하는 문제는 연습문제를 제외하고 총 7문제였다.

Note_ 5648번 역원소 정렬 : 숫자가 커서 long long을 사용해야 했고 따라서 stoi가 아닌 stoll을 사용해야 했다.

7795번 먹을 것인가 먹힐 것인가 : 정답 코드가 보면 좋을 것 같은 코드.

리뷰

카운팅 소트는 처음 배우는 부분이였는데 개념적으로는 생소하지 않았고, 지금까지 써왔던 방식이여서 어렵지 않았다.

정렬부분을 다시 리마인드 할 수 있었고 문제를 풀어본 뒤에 빠르게 진도를 나가야겠다.

가볍게 정리하고 다음은 0X10 다이나믹 프로그래밍으로 돌아오겠다.

출처: 바킹독님의 실전알고리즘 강의

PS 시리즈26편