728x90 반응형 Computer Science (CS)14 [Computer Science] 기수 정렬 기수정렬 (Radix Sort) 개념 기수 정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. 정렬 방식 0~9까지의 Bucket(Queue 자료구조)을 준비한다. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다. 0부터 차례대로 버킷에서 데이터를 다시 가져온다. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다. 먼저 1의 자리 숫자부터 시도를 합니다. 데이터 순서대로 각 1의 자리에 해당되는 Qu.. 2023. 11. 26. [Computer Science] 카운팅 정렬 Counting Sort 계수정렬은 O(n)의 시간복잡도를 갖는다 일반적 상황에서 가장 빠른 정렬 알고리즘인 Quick Sort는 O(nlogn)을 가진다 그렇다면 대부분의 정렬이 필요한 상황에서 카운팅정렬을 사용하지 않고 퀵정렬을 사용할까?? 정렬과정 첫번째로 각 숫자가 몇 번 등장하는지 세어준다. 등장 횟수의 누적합을 구해준다 여기서 누적합의 의미를 알아보자 숫자 0은 0번째 index에서 1번째 사이에 위치한다 ( 0 ) 숫자 1은 1번째 index에서 4번째 사이에 위치한다 (1 , 2 , 3) 숫자 2는 4번째 index에서 4번째 사이에 위치한다 ( X ) 숫자 3은 4번째 index에서 6번째 사이에 위치한다 (4, 5) 누적합을 이용해 정렬 (안정정렬을 만들기 위해 a의 맨 뒤에서부터 정렬.. 2023. 11. 26. [Computer Science] 퀵 정렬 기본 퀵 정렬 퀵 정렬(quick sort)은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다. 퀵정렬을 위한 데이터 ① 맨 앞의 20을 기준키로 하고, 기준키 다음부터 기준키보다 큰 데이터를 찾아 50을 선택하고, 마지막 데이터부터 기준키보다 작은 데이터를 찾아 5를 선택한다. 그리고 선택된 50과 5를 교환한다. ② 계속해서 진행하여 기준키보다 큰 데이터인 40을 선택하고, 기준키보다 작은 데이터인 19를 선택한다. 그리고 두 수를 교환한다. ③ 마찬가지로 진행하여 기준키보다 큰 데이터인 40과 기준키보다 작은 데이터인 9를 선택한다. 그런데 발견된 위치가 서로 교차하는데,.. 2023. 11. 19. [Computer Science] 정렬(선택, 버블, 삽입) 정렬이란? 물건을 크기 순으로 나열하는 것 (오름, 내림차순) 많은 정렬 알고리즘들이 존재 단순하지만 긴 수행시간 : 삽입정렬, 선택정렬, 버블정렬 복잡하지만 짧은 수행시간 : 퀵정렬, 히프정렬, 합병정렬, 기수정렬 모든 경우에 최적인 알고리즘은 없음 → 환경에 맞추어 선택! 정렬 알고리즘의 평가 비교 횟수 이동 횟수 안정성 선택정렬 (selection sort) 정렬이 안된 곳에 최소값 선택 → 정렬된 끝 위치와 교환 시간복잡도 : O(n^2) 최소값 선택 : O(n) 최종 : 최소값 선택 * n번 반복 = O(n^2) // 선택 정렬 void selection_sort(int list[], int n){ int i, j, least, temp; // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수.. 2022. 10. 10. [Computer Science] 힙(Heap) 힙이란? 완전 이진 트리 완전 이진 트리이면서 heap property를 만족하는 자료구조이다. 우선 순위 큐를 위한 것이다. 최댓값 혹은 최솟값을 쉽게 구할 수 있다. 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 가장 오른쪽부터 연속된 몇 개의 노드가 비어있을 수 있다. 힙의 종류 최대힙 혹은 최소힙을 만족해야한다. 최대힙(max heap property) : 부모는 자식보다 크거나 같다. → 최대값을 찾는데 시간복잡도 O(1) 최소힙(min heap property) : 부모는 자식보다 작거나 같다. → 최소값을 찾는데 시간복잡도 O(1) 예시 (a)는 3가지 모두 다 완전이진트리와 최대 힙의 특성을 만족한다. (b)는 완전이진트리지만 최대힙 혹은 최소힙 특성을 만족하지 않는다. (c).. 2021. 10. 14. [Computer Science] B-트리(B-Tree) B-Tree B-Tree는 ORACLE과 같은 상용 DB에서 많이 사용하는 자료구조이며 외부검색에 유용하다고 알려짐, 이진 트리를 확장한 구조이다. 특성 M차 B-Tree의 높이는 $log_{m/2}N$ 즉, O(logN)의 성능 한 노드에 M개의 자료, M+1개의 자식을 가질 수 있음 외부검색에 적합 하나의 노드크기를 Disk I/O 단위의 크기로 하나의 노드가 다량의 데이터를 가질수 있기에 입출력시에 불러오는 블럭의 크기만큼 노드의 크기를 설정한다면 외부기억장치에 접근하는 횟수가 줄어들기 때문에 데이터를 빠르게 처리할 수 있다. https://www.cs.usfca.edu/~galles/visualization/BTree.html 이진 트리의 한계 : 두 개의 자식밖에 가지질 못하고 자칫 균형이 맞지.. 2021. 10. 14. 이전 1 2 3 다음 728x90 반응형
