반응형 분류 전체보기340 [알고리즘] Sorting in leanar time(선형시간 알고리즘) Sorting in leanar time(선형시간 알고리즘) 앞서 보았던 예제를 제외한 정렬 알고리즘을 보자. 먼저 count 알고리즘이다.count 알고리즘의 조건은 다음과 같다.1) n개의 정수를 정렬하라(단, 모든정수는 0에서 n사이의 정수이다.)예) n명의 학생들의 시험 점수를 정렬하라. 단 모든 점수는 100 이하의 양의 정수이다. k이하의 정수라는 사전정보가 있고 이 정보를 이용하여 정렬하므로comparison sort가 아니다. count 알고리즘은 k 가 비교적 작을때 적용할 수있는 알고리즘이다.따라서 k가 5일때 예를 들어 알아보도록 하자 이 때, C라는 배열은 카운터이다.카운트 알고리즘은 입력 배열을 처음부터 끝까지 스캔하면서그 값들이 각각 몇개가 있는지 카운트해서 C라는 배열에 저장해.. 2017. 4. 19. [알고리즘] Sort - 정렬의 Low Bound Sort - 정렬의 Low Bound 앞서 여러가지 정렬을 살펴보았다.그 결과 다음과 같은 질문을 할수 있을것 가다.과연 O(nlogn)이라는 시간복잡도가 최선일까 미리 결론을 이야기하자면 O(nlogn)보다 더 나은 시간복잡도는 없다는 것이다.여기에는 한가지 전제조건이 붙는데Comparison sort(비교 정렬)에 대해서는 보다 더 나은 복잡도가 없다는 것이다. 그렇다면 comparison sort는 무엇일까comparison sort는 데이터와의 크기 관계만을 이용해서 정렬하는 알고리즘이다.따라서 데이터들의 크기관계가 정의되어있다면 어떤 데이터 형 에서도 적용이 가능하다(문자, 알파벳, 사용자 정의 객체 등)따라서 앞서 살펴본 버블, 삽입, 선택, 퀵, 힙 정렬들이 모두 해당된다고 볼 수 있다. 이.. 2017. 4. 19. [알고리즘] Sort - Heap의 응용, 우선 순위 큐(Priority queue) Sort - Heap의 응용, 우선 순위 큐(Priority queue) 큐는 여러개의 데이터를 넣을수 있는 컨테이너이다.데이터가 들어오고 나갈때는 First In First Out(FIFO) 구조를 가진다. 우선 순위 큐는 이러한 큐의 한종류로써최대 우선 순위 큐와 최소 우선 순위 큐로 나뉜다.우리는 최대 우선 순위 큐를 중심으로 알아보도록 하겠다. 최대 우선순위큐는 다음의 두가지 연산을 지원하는 자료구조이다.1) INSERT(x) : 새로운 원소 x 를 삽입2) EXTRACT_MAX : 최대값을 삭제하고 반환 반대로 최소 우선 순위큐는 EXTRACT_MAX대신 EXTRACT_MIN을 지원한다.MAX HEAP을 이용해서 최대 우선 순위 큐를 구현할 수있다. 먼저 INSERT에 대해서 알아보도록 하자위의.. 2017. 4. 19. [알고리즘] Sort - 힙정렬(heap sort) - 2 Sort - 힙정렬(heap sort) - 2 이번 시간에는 heap과 heapify연산을 이용해서어떻게 heap 정렬을 할것인지 알아 볼것이다. 그 전에 정렬을 하기 위해서는 heap을 만들어야한다.정렬할 1차원 배열을 complete binary tree로 해석한다tree로 만든다는 것이 아니라 개념적으로 받아들인다는 뜻이다. complete binary tree는 heap property를 만족하지 않기때문에heap은 아니다.그러므로 부모가 자식보다 크다 라는 조건이 자동으로 성립되지 않는다. 따라서, 정렬의 첫번째 조건은 complete binary tree을 heap으로 만드는 것이다.leaf가 아닌 그 다음 레벨의 노드에서부터 heapify 연산을 통해서 heap으로 만들어준다. 1234BUI.. 2017. 4. 19. 이전 1 ··· 56 57 58 59 60 61 62 ··· 85 다음 반응형
