계수 정렬(Counting Sort)의 핵심 아이디어와 특징은?

어려움 freeCodeCamp

보기 및 정답

A 각 값의 등장 횟수를 세어 정렬하며, 비교 기반이 아니므로 O(n+k) 시간에 정렬할 수 있다 (k는 값의 범위)

B 모든 데이터 유형에 대해 항상 O(n log n)으로 동작하며, 비교 기반 정렬 중에서 가장 효율적이다

C 원소 간의 대소 관계를 직접 비교하여 교환하는 비교 기반 정렬이며, 평균 시간 복잡도는 O(n log n)에 해당한다

D 실수(float) 데이터의 소수점 이하 자릿수를 기준으로 분류하여 정렬하므로, 실수 데이터에 가장 적합하다

계수 정렬은 데이터의 각 값이 몇 번 나타나는지 세는 카운트 배열을 만들고, 이를 기반으로 정렬합니다. 값의 범위(k)가 작을 때 매우 효율적이지만, k가 매우 크면 메모리 낭비가 됩니다. 정수나 제한된 범위의 데이터에 적합합니다.

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

로그인