강의

https://youtu.be/dq5t1woLJMw?si=TnquGAhv_QEuNAkC

설명

Counting Sort

$O(N+K)$

오 저번에 10989 문제가 counting sort로 푼 거였구나
빈도수를 저장해놓고 오름차순대로 빈도수만큼 숫자를 출력해주면 된다.

단점은 수의 범위에 해당하는 배열이 필요하다.

수의 범위가 1000만 이하일 때엔 카운팅 소트를 쓰고 그렇지 않을 때는 못 한다고 생각하면 될 것 같다.

Radix Sort 기수정렬

$O(D(N+K))$
D: 자릿수

자릿수를 이용해서 정렬 하는 알고리즘. 카운팅 소트를 응용한 알고리즘
1의 자리부터 오름차순으로 배열을 재정렬해가면서 진행.

기수정렬은 코테에선 구현할 일이 전혀 없다~~ 개념 정도만 알아두기

코테에선?

코딩테스트에선 굳이 직접 짤 필요가 없다~~ STL sort()를 이용하기!

주의사항

비교함수 인자로 그냥 값을 전달하면 복사가 일어나기 때문에 불필요한 연산이 생김.
레퍼런스로 전달해야 불필요한 연산을 줄일 수 있다. 큰 차이는 아니지만 알아두기

중요한 건 1번 주의사항

문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0F.md

11652

주의: !!입력 받는 수의 범위가 int 범위를 초과하기 때문에 long long형으로 선언해야 한다!!
int형 4byte. 32bit. 2^32(-2^31 ~ 2^31 - 1)

1431

comp 함수 커스텀해서 원하는 대로 비교할 수 있도록 연습

5648

알아갈 것 : reverse() 함수가 있었다ㅠㅠ 문자열 뒤집어주는 함수가 이미 있었음

1181

그냥 comp 함수 커스텀해서 조건대로 정렬되게 하고, 중복인 경우 출력 안 하고 건너뛰었음

2910

https://github.com/zhy2on/practice-algorithm/blob/main/BaaarkingDog/0x0f/2910.cpp

10814

간단한 문제

11656

간단한 문제

10825

와.. 첨엔 comp 함수를 조건에 맞게 만들어서 풀었는데

bool comp(const student &a, const student &b) {
	if (get<1>(a) != get<1>(b)) return get<1>(a) > get<1>(b);
	if (get<2>(a) != get<2>(b)) return get<2>(a) < get<2>(b);
	if (get<3>(a) != get<3>(b)) return get<3>(a) > get<3>(b);
	return get<0>(a) < get<0>(b);
}

그냥 감소순인 건 음수로 바꿔서 저장해주면 커스텀 함수 굳이 안 쓰고도 sort함수로 할 수 있었다.
https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0F/solutions/10825.cpp

7795

간단한 문제