[바킹독 알고리즘] 0x0F - 정렬 II

0x00 Counting sort

 

 

그냥 각 수의 등장 횟수만 세어 정렬하면 된다. 정렬 알고리즘 중에서 가장 쉽다. 하지만 이 알고리즘은 만능이 아니다. 일단 카운팅 소트를 쓰려고 하면 각 수의 등장 횟수를 저장해야 한다. 그리고 등장 횟수를 세는 방법은 미리 큰 테이블을 만들어두고 수에 대응되는 원소의 값을 1 증가시켜서 처리하는 것이다. 만약 수가 0에서 9 사이라고 한다면 freq[10] 배열을 선언해서 처리할 수 있고 수가 0에서 9999사이라고 한다면 freq[10000] 배열을 선언해서 처리할 수 있다.

 

만약 수의 범위가 0에서 999,999,999 까지라고 하면 크기가 10억인 배열이 필요하므로 Counting Sort는 수의 범위가 대략 1000만 이하일때에만 쓰인다.

 

시간복잡도는 O(N+K),,,    K는 범위 속 가능한 값들

 

 

 

 

 

BOJ 15688번: 수 정렬하기5

15688번: 수 정렬하기 5

 

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

int freq[2000005];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        freq[a+1000000]++;   //a의 범위가 절대값이므로 이를 처리하기위해 100만을 더했다
    }
    for(int i=0; i<= 2000000; i++){
        while(freq[i]--){
            cout << i-1000000 <<'\n';
        }
    }
}

 

 

 

 

 

 

 

0x01 Radix Sort

자릿수를 이용해서 정렬을 수행하는 알고리즘으로, Counting Sort를 응용한 알고리즘이라고도 생각할 수 있다.

 

그냥 리스트를 가지고 먼저 1의 자리 순으로 재배열하고, 그 다음 10의 자리 순으로 재배열하고, 마지막으로 100의자리 순으로 재배열 하면 3자리 수의 리스트가 정렬이 된다.  아래 두 사진은 예시이다.

 

 

 

 

 

 

 

 

구현을 할 바엔 STL sort를 사용하는게 훨씬 낫지만 굳이 구현을 해본다면 다음과 같다.

 

 

거듭 제곱을 계산하기 위해 pow를 사용할때 주의점은 pow는 실수형을 반환하는 함수이기 때문에 실수 오차로 인해 꼬여버릴 수 있다. 정수 거듭제곱을 계산해야 하면 위 18, 19번째 줄처럼 해야한다.

 

 

 

시간복잡도는 O(DN),,,,,,  D는 자릿수의 최대 개수

 

 

 

 

 

Comparison Sort, Non-comparison Sort

 

Comparison Sort 는 원소들끼리 크기를 비교하는 과정이 있음.

Non-comparison Sort 는 원소들간의 크기를 비교 하지 않고 정렬을 수행함.

 

 

 

 

 

0x02 STL sort

코딩테스트에서는 직접 정렬을 짜지 않고 STL을 이용해야 한다.

 

 

 

배열의 경우 1, 2번째 줄 처럼, vector에서는 4, 5번째 줄처럼 사용한다. 배열에서는 인자로 포인터 2개를 넘겨주는데 예를 들어 7을 가리키려고 한다면 2번째 줄 처럼 a+4 가 아닌 a+5를 넘겨줘야 한다. vector에서는 배열.begin()과 배열.end()를 이용할 수 있다.

 

STL sort는 Quick sort를 기반으로 하지만 리스트가 불균등하게 쪼개지는 상황이 계속 반복되어서 재귀에서의 깊이가 너무 깊어지면 O(NlgN)이 보장되는 정렬 알고리즘으로 처리한다. 그래서 STL sort는 최악의 경우에도 O(NlgN)이 보장되기 때문에 맘편히 써도 된다. 

 

STL sort는 stable sort가 아니다. 그래서 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않을 수 있다.

 

pair, tuple 에는 대소 관계가 먼저 앞의 원소의 대소를 비교하고 값이 같으면 그 다음 원소의 대소를 비교하는 방식으로 정해져있다. 예를 들어 pair에서 {2, 5} < {3, 2} 고 tuple에서 {2, 1, 0} > {2, -2, 6} 이다. 그래서 좌표를 정렬하거나 기타 여러 속성이 있는 원소를 정렬할 때 별도로 구조체를 둘 필요가 없고 pair나 tuple 등을 이용하면 된다.

 

 

 

 

 

 

STL sort는 비교 함수를 내가 정해서 넘겨줄 수 있다. 위 예시는 int형을 크기 순으로 정렬 하고 싶은데 추가적인 정렬 조건으로 int형을 5로 나눈 나머지 순으로, 5로 나눈 나머지가 같다면 크기 순으로 정렬하겠다는 것이다. 이렇게 하면 배열 a가 5, 1, 6, 2, 7, 3, 4 로 정렬된다. 이처럼 비교 함수 cmp(int a, int b)는 a가 b의 앞에 와야 할 때 true, 반대는 false를 반환한다.

 

 

 

 

주의사항

 

비교 함수에서 주의해야 할 점 첫 번째는 a가 b의 앞에 와야할 때만 true를 반환해야 하니 두 값이 같을 때 혹은 우선순위가 같을 때에는 반드시 false를 반환해야 한다.

 

예를 들어 수열을 크기 내림차순으로 정렬하고 싶을 때 왼쪽과 같이 비교 함수를 작성하면 겉으로는 문제가 없어보이지만 a와 b가 같을 경우 true를 반환하기 때문에 오류 발생할 수 있다. 오른쪽 처럼 변경하는것이 이 문제에서 꼭 두 값이 같응ㄹ 때 false를 반환해야하는 것처럼 해야 오류(런타임에러)를 줄일 수 있다.

 

 

 

 

두 번째는 reference에 관한 부분이다.  문자열을 받아서 끝자리의 알파벳 순으로 정렬하고 싶다고 하면 비교 함수를 왼쪽과 같이 작성하면 결과가 정상적으로 나온다. 그런데 이렇게 작성을 하면 별로 바람직하지 않다. 함수의 인자로 STL이나 구조체 객체를 실어서 보내면 값의 복사가 일어나는데 지금 이 비교 함수를 생각해보면 굳이 복사라는 불필요한 연산을 추가로 하면서 시간을 잡아먹을 필요가 없다. 그래서 복사를 하는 대신 reference를 보내는게 더 바람직하다.

 

 

비교함수 연습 문제

BOJ1431번: 시리얼 번호

1431번: 시리얼 번호

 

 

 

 

 

 

 

 

0x03 정렬의 응용

BOJ 11652번: 카드

11652번: 카드

 

 

 

 

 

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

int n;
long long a[100005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a, a+n);
    int cnt = 0;
    long long mxval = -(1ll << 62)-1;   //-2^62 -1 비트연산자 << 를 이용해 표현한것
    int mxcnt = 0;
    for(int i=0; i<n; i++){
        if(i==0 || a[i-1] == a[i]) cnt++;
        else{
            if(cnt > mxcnt){
                mxcnt = cnt;
                mxval = a[i-1];
            }
            cnt = 1;
        }
    }
    if(cnt > mxcnt) mxval = a[n-1];
    cout << mxval;
}