728x90
1. 계수 정렬
- 데이터가 몇 번 나왔는지 세어 정렬하는 방식이다.
- 시간 복잡도가 O(n)으로 매우 빠르다.
- 수의 범위가 클수록 메모리 낭비가 심하다.
2. 계수 정렬 과정
- 각 데이터가 나온 횟수를 count array에 저장한다.
- count array의 누적합 배열을 만든다.
- 누적합 배열을 이용하여 정렬된 배열을 만든다.
3. 예제 문제
[2750] 수 정렬하기 (JAVA)
# 문제 설명 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이
spicyrisotto.tistory.com
728x90
'책 > Do it! 알고리즘 코딩 테스트 자바 편' 카테고리의 다른 글
| Day-8 너비 우선 탐색 BFS (0) | 2024.03.29 |
|---|---|
| Day-8 깊이 우선 탐색 DFS (0) | 2024.03.29 |
| Day-7 기수 정렬 (0) | 2024.03.27 |
| Day-7 병합 정렬 (0) | 2024.03.27 |
| Day-6 퀵 정렬 (0) | 2024.03.27 |
