노트

이 글은 인프런의 영리한 알고리즘을 위한 프로그래밍 강좌를 듣고 정리한 내용입니다. Counting Sort(계수 정렬)항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형 시간에 정렬하는 효율적인 알고리즘- n개의 정수를 정렬하라. 단 모든 정수는 0에서 k 사이의 정수이다.- 예 : n 명의 학생들의 시험 점수를 정렬하라. 단, 모든 점수는 100 이하의 양의 정수이다. 의사코드 Counting-Sort(A, B, k) {for i

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. 정렬의 Lower Bound정렬 알고리즘의 유형 Comparison Sort- 데이터들 간의 상대적 크기 관계만을 이용해서 정렬하는 알고리즘- 따라서 데이터들 간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능(문자열, 알파벳, 사용자 정의 객체 등)- 버블 소트, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등 Non-Comparison Sort- 정렬할 데이터에 대한 사전 지식을 이용 - 적용에 제한- Bucket Sort- Radix Sort 정렬 문제의 하한어떠한 경우에도 모든 Comparison Sort의 시간복잡도는 Θ(nlogn) 보다 낮을 수 없다를 증명 하한(Lower Bound)- 입력된 데이터를..

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Priority Queue(우선순위 큐)힙의 응용 : 우선순위 큐최대 우선순위 큐(Maximum Priority Queue)는 다음의 두 가지 연산을 지원하는 자료구조이다.- INSERT(x) : 새로운 원소 x를 삽입- EXTRALT_MAX() : 최대값을 삭제하고 반환 최소 우선순위 큐(Minimum Priority Queue)는 EXTRALT_MAX 대신 EXTRALT_MIN을 지원하는 자료구조이다.- MAX HEAP을 이용하여 최대 우선순위 큐를 구현 INSERT 연산 의사코드 MAX-HEAP-INSERT(A, key) { // A : heapheap_size = heap_size - 1;A[heap_size] =..

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Heap Sort(힙 정렬)힙 정렬이란 최대 힙이나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.2. 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드로부터 구성하며 아래 부터 루트까지 올라오며 순차적으로 만들어갈 수 있다.3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.4. 2와..

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Quick Sort(퀵 정렬)퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행한다. 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한다.1. 리스트 가운데 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.2. 피벗 앞에는 피벗보다 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.3. 분할된 두 개의 작은..