728x90 반응형 Computer Science12 [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] 큐(Queue), 덱(Deck) 큐(Queue) 선입선출 (FIFO - First In First Out) Rear : 가장 뒤 ( 데이터가 들어오는 위치) Front : 가장 앞 ( 데이터가 나가는 위치) ex) 버스를 기다리는 줄, 은행에서 업무를 보기위해 기다리는 줄 등등 Enqueue : 큐 맨 뒤에 어떠한 요소를 추가, 마지막으로 온 손님에게 번호표 발부 Dequeue : 큐 맨 앞쪽의 요소를 삭제, 창구에서 서비스를 받은 손님의 번호표를 대기목록에서 삭제 Peek : front에 위치한 데이터를 읽음, 다음 서비스를 받을 손님이 누구인지 확인 front : 큐의 맨 앞의 위치(인덱스), 다음 서비스를 받을 손님의 번호 rear : 큐의 맨 뒤의 위치(인덱스), 마지막에 온 손님의 번호 선형큐 1차원 배열을 이용 인덱스를 값으.. 2021. 9. 13. 이전 1 2 다음 728x90 반응형
