Counting Sort

수를 정렬하고 등장횟수를 저장한다.

수의 범위가 어느정도 한정적일 때에만 카운팅 소트를 사용할 수 있다.

ex 수의 범위가 10억이 넘는 경우 int로 잡아도 1.2억개의 수 만 저장 가능하고 이때 저장을 한다고 치면 512mb를 넘어가게 된다.

범위가 작을 떄 사용하면 굉장히 효율적인 코드가 나온다.

15688번: 수 정렬하기 5

Radix Sort(O(DN))

일의자리 , 십의 자리, 백의자리에 맞춰서 인덱스에 넣고 배열을 수행한다.

라딕스 소트의 맹점

라딕스 소트에서 데이터를 넣는 저장공간은 배열이 아닌 동적리스트여야 한다.

배열의 공간이 정확히 얼마나 필요한지 알 수 없기 떄문에 크기를 무작정 크게 지정하게 된다면 공간낭비가 생기게 된다.

STL sort

sort는 퀵소트 기반으로 생성되었다. O(NlgN)을 가지지만 최악의 경우 N^2의 정렬알고리즘을 갖는다. 또한 stable_sort가 아니기 때문에 (우선순위가 같을때 원소의 위치가 보장되어 있지 않다.) stable_sort가 필요한 상황에서는 sort대신 stable_sort를 사용하자 사용법은 sort와 같다.

비교함수 인자

주의 사항

1. 값이 복사되기 때문에 굳이 복사하지 않고 reference를 주는 것이 좋다.

두 값이 같을 때!! false를 리턴함

활용 문제

#include <iostream>
#include <algorithm>;
#include <queue>;
#include <cstdlib>
#include <vector>
using namespace std;

/*
 *[문제]
 *준규가 가장 많이 가지고 있는 숫자를 적는다.
 *
 *[입력]
 *1<= N <= 100000
 * [IDEA]
 * 정렬 한다.
 * 수를 index로 사용하고 ++한다. 범위는 long long으로 한다.
 */

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

    int n; cin >>n;
    long long store[n];
    for(int i=0; i<n; i++) {
        cin >> store[i];
    }

    sort(store, store+n);

    long long maxval =-(111<<62)-1;
    int maxcnt=0;
    int cnt=1;

    for(int i=1; i<=n; i++) {
        if(store[i] !=store[i-1]) {
            if(cnt>maxcnt) {
                maxcnt = cnt;
                maxval = store[i-1];
            }
            cnt=1;
        }else cnt++;
    }

    cout << maxval;
}

[바킹독의 실전 알고리즘] 0x0F강 - 정렬 II