무딘붓의 코딩기록

카운팅 정렬 (Counting Sort) 카운팅 정렬 (Counting Sort)은 정렬할 수의 범위가 작은 경우 사용하는 정렬으로, 시간 복잡도가 O(n)인 매우 빠른 정렬입니다. 단점은 수의 범위가 커지면 사용하는 메모리도 그만큼 커진다는 단점이 있습니다. (이때문에 수의 범위가 작은 경우에 사용) 작동 원리 카운팅 정렬의 원리는 간단합니다. 정렬할 원소를 하나씩 살펴보고, 그 원소 값에 해당하는 배열에 카운트를 1 늘려주면 됩니다. 카운팅 정렬이 작동하는 방식을 GIF로 만들어 보았습니다. 위의 그림에서는 배열의 크기가 10,000개나 되지만, 실제 입력 값의 최대 크기는 7이므로 그만큼 크기를 줄여도 작동합니다. 반대로, 입력값에 100,000,005 같이 큰 수가 나온다면, 그만큼 배열이 커져야..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net [소스코드] #include #include #include using namespace std; // [baekjoon] 1181번 - 단어 정렬 // 2023.01.04 bool compare(string a, string b) { if (a.length() == b.length()) {// 길이가 같으면 return a < b;// b가 사전순으로 a 보다 다음 순서가 되게 정렬 ..

C++에서는 쉬운 정렬을 위해 sort함수가 지원됩니다. C언어에서도 stdlib.h 헤더파일을 선언하여 qsort()를 사용할 수 있지만, C++의 sort() 함수는 이와는 조금 다릅니다. sort C++에서 sort()함수는 헤더파일을 추가한 다음 사용할 수 있습니다. 이 sort 정렬 함수는 최악의 경우에도 O(nlogn)의 시간 복잡도를 가지는 intro sort 정렬 알고리즘을 이용합니다. intro sort 알고리즘은 quick 정렬 알고리즘을 기반으로, heap sort와 insertion sort를 혼합해 만든 알고리즘이라고 합니다. quick 정렬의 경우는 최악의 경우 O(n^2) 시간복잡도를 가지므로, 더 빠르게 사용할 수 있다는 장점이 있네요. sort 함수의 사용방법을 알아보겠습니..

https://www.acmicpc.net/problem/25305 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net [소스코드] #include #include using namespace std; // [baekjoon] 25305번 - 커트라인 // 2023.01.04 int main() { int arr[1001] = { 0 }; int n, k, x; cin >> n >> k; for (int i = 0; i > arr[i]; } sort(arr, arr + n, greater()); cout