버킷정렬, 기수정렬, 계수정렬은 비교에 기반하지 않는 정렬 방법으로 시간복잡도 O(nlogn)보다 빠르게 구현하고자 제안된 정렬 알고리즘이다. 오늘은 기수정렬과 계수정렬에 대해 알아보고자 한다. 간단하니까 툭툭 치고 넘어간다. 📌 기수정렬 Radix Sort 기수정렬의 핵심은 낮은 자리에서 높은 자리로 기준을 바꾸어 가며 정렬하는 것이다. stable sort가 적용된 대표적인 정렬로 이전의 정렬 순서가 바뀌지 않는다. 실제로 정렬을 한다기보다 자릿수에 맞게 0~9까지의 버킷이 있고 이 버킷에 해당하는 자릿수를 포함한 수를 넣는 방식이다. 자리를 바꿔가며 버킷에 넣는 걸 반복하면 자동적으로 정렬이 되는 원리이다. 이때 버킷은 Queue(큐, First In First Out) 방식을 사용한다. 이때 이전..
📌 퀵정렬 퀵정렬은 가장 널리 쓰이는 정렬 알고리즘으로 말 그대로 빠른 정렬이 가능하다. 퀵 정렬도 병합정렬과 마찬가지로 분할정복기법을 이용한 알고리즘이다. 퀵 정렬의 핵심 아이디어는 특정 원소를 기준으로 작은 데이터와 큰 데이터를 분류한다는 것이다. 이렇게 되면 특정 원소를 기준으로 순서가 결정되며 분류된 작은 데이터와 큰 데이터 안에서 각각 기준 원소를 다시 정해 재귀적으로 쪼개나가면서 정렬해나간다. 병합정렬과 마찬가지로 단위를 쪼개나가는 아이디어이므로 분할정복기법이라고 할 수 있다. 이때 생각해봐야 할 것은 기준이 되는 원소(pivot)를 어떻게 정하느냐 인데, 1) 첫번째 원소를 기준으로 하거나 2) 랜덤으로 원소를 선택한다 첫번째 원소를 기준으로 할 경우 이미 정렬된 리스트의 경우 피봇의 한쪽에..
🧨 문제 출처 문제 출처 : 백준 2752번 문제 난이도 : 브론즈 4 문제 링크 : www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net 🧨 알고리즘 선택 및 C++ 코드 세 개의 수를 입력해 오름차순 정렬하는 문제다. 사실상 N개의 수를 입력해 오름차순 정렬하는 것과 별반 다르지 않은 문제인데 왜 브론즈 4인지는 의문이다. 다른 방법으로 더 간단하게 구현하는 방법이 많을 거다. 사실 3개의 수라면 복잡하게 정렬 알고리즘을 따지지 않고 2번 또는 3번만 비교해도 대중소를 가려낼 수 있긴 하다. 정렬 알고리즘 공부하면서 구현한거라 그냥 병합..
코테 문제를 풀면서 꼭 필요한 알고리즘 기법 중 하나가 정렬이라고 할 수 있다. 일반적으로 문제에 따라 (시간복잡도를 고려한) 적절한 정렬 알고리즘을 공식처럼 사용한다. 그 전에 자주 쓰는 정렬 알고리즘 종류와 시간복잡도를 계산했다. 📌 버블정렬 (Bubble Sorting) 맨 왼쪽 원소부터 바로 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로 가도록 교환하는 정렬방식이다. 거품정렬이라고도 하며 두 인접한 원소를 비교하는 것이 핵심이다. 시간복잡도는 O(n^2)이지만 구현이 쉬워 자주 사용된다. TMI) 양방향으로 번갈아 수행하면 칵테일 정렬이라고 한다. 이해하기 쉽도록 { 8, 3, 9, 7 6 } 배열을 오름차순 정렬하는 것을 예로 들었다. 버블정렬은 이해하기도 쉽고 구현하기도 쉬워서 자주 쓰이..
