개발자의 기록습관

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-8. Radix SortCounting sort와 마찬가지로 non-comparison Sort이다.Radix Sort의 기본가정ex) n개의 d자리 정수들 - 길이가 d인 문자열이며 각각의 문자들이 가질수 있는 값의 갯수가 상수개 이다.꼭, 정수일 필요는 없으며 길이가 d인 영문자도 가능하다.가장 낮은 자리수부터 정렬한다.d=3, n=7각각의 단계가 진행될 때, 반드시 stable해야 한다."입력에 동일한 값이 있을때 입력에 먼저 나오는 값이 출력에서도 먼저 나온다."라는 성질을 만족해야 한다.예를 들어서, 두번째 단계에서 세번째 ..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-7. Counting Sort - 선형시간 정렬 알고리즘선형시간 = O(n)즉, comparison sort가 아니다.(comparison sort의 하한은 O(nlogn)이다.)Sorting in Linear TimeCounting Sortn개의 정수를 정렬하라. 단 모든 정수는 0에서 k사이의 정수이다.예) n명의 학생들의 시험점수를 정렬하라. 단 모든 점수는 100이하의 양의 정수이다.k=5인 경우의 예배열 C는 counter 배열codeA[] - 정렬할 데이터C[] - counter 배열 int A[n]; int C[k] = ..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-6. 정렬의 하한(lower bound)Comparison SortO(n²)bubble sortselection sortinsertion sortquick sort(최악의 경우. 평균은 O(nlogn))O(nlogn)merge sortheap sortO(nlogn)보다 시간복잡도가 더 낮은 comparison 정렬 알고리즘은 존재할 수 없다는 것이 이번 학습에서 얻을 수 있는 결론이다. 정렬 알고리즘의 유형Comparison sort데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘따라서 데이터들간의 크기 관계가 정의되어 있으..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-5. 우선순위 큐(priority queue)힙의 응용: 우선순위 큐최대 우선순위 큐(maximum priority queue)는 다음의 두 가지 연산을 지원하는 자료구조이다.INSERT(x) : 새로운 원소 x를 삽입EXTRACT_MAX(): 최대값을 삭제하고 반환최소 우선순위 큐(minimum priority queue)는 EXTRACT-MAX대신 EXTRACT-MIN을 지원하는 자료구조MAX HEAP을 이용하여 최대 우선순위 큐를 구현INSERTmax heap의 형태로 원소들이 저장되어 있고, 15가 insert되는 경우 아래와..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-4. 힙 정렬(Heap Sort)Heap과 Heap sort최악의 경우 시간복잡도 O(nlogn)Sorts in place - 추가 배열 불필요mergesort도 최악의경우 O(nlogn)이었지만, 추가 배열이 필요했음.이진 힙(binary heap) 자료구조를 사용O(nlogn)의 시간복잡도를 가지면서, merge sort처럼 추가적인 배열이 필요하지 않기 때문에 좋은 정렬 알고리즘 중 하나다.Heap의 정의Heap은완전 이진 트리(complete binary tree)이면서Heap property를 만족해야 한다.동일한 데이터를 ..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-3. 빠른정렬(Quick Sort)분할정복법분할배열을 다음과 같은 조건이 만족되도록 두 부분으로 나눈다.기준값 : pivotelements in lower parts =r일 때, 정렬할 데이터가 0개 또는 1개이므로 할 일 없음. if (p = x j