범위 조건이 있는 경우에 굉장히 빠른 알고리즘
시간 복잡도: O(N)
단순하게 '크기를 기준으로' 세는 알고리즘
예시) 숫자는 1에서 5사이의 정수
1 3 2 4 3 2 5 3 1 2 3 4 4 2 5 1 2 3 5 2 3 1 4 3 5 2 1 1 1
1이 몇 개인지, 2가 몇 개인지.... 5가 몇 개인지 셈
#include <stdio.h>
int main(void){
int temp;
int count[5];
int arr[30] = {
1, 3, 3, 5, 2, 3, 4, 2, 4, 4,
5, 3, 4, 2, 1, 1, 2, 3, 5, 3,
2, 4, 4, 1, 2, 3, 3, 2, 5, 3};
// 배열 초기화
for(int i = 0; i<5; i++){
count[i] = 0;
}
for(int i = 0; i<30; i++){
count[arr[i]-1]++;
}
for(int i = 0; i<5; i++){
if(count[i] != 0){
for(int j = 0; j<count[i]; j++){
printf("%d ", i+1);
}
}
}
return 0;
}
'컴퓨터기본 > 알고리즘' 카테고리의 다른 글
7. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) (0) | 2021.06.14 |
---|---|
6. 스택 (Stack), 큐 (Queue) (0) | 2021.06.14 |
4. Heap Sort (힙 정렬) (0) | 2021.06.14 |
3. 퀵 정렬 (Quick Sort), 병합 정렬 (Merge Sort) (0) | 2021.06.14 |
2. O(n²) 알고리즘(선택, 버블, 삽입 정렬) (0) | 2021.06.14 |