알고리즘, 자료구조15 Heap 자료구조 [Python / 파이썬] -목차- 1. Heap 자료구조란? 2. 힙(heap)의 삽입 3. 힙(heap)의 삭제 4. 파이썬 힙 자료구조 4.1 heapq 모듈의 주요 메서드 4.2 파이썬에서 최대 힙 사용하기 1. Heap 자료구조란? 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다. A가 B의 부모노드(parent node) 이면, A의 키(key) 값과 B의 키값 사이에는 대소 관계가 성립한다. 힙에는 두가지 종류가 있으며, 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙을 '최대 힙', 부모 노드의 키값이 자식 노드의 .. 2022. 3. 20. Tim Sort -목차- 1. Tim sort의 등장 2. Tim sort의 기본 원리 3. Tim sort의 최적화 기법 3.1 Run 3.2 Binary Insertion Sort 3.3 Merge 4. Galloping 참고 자료 1. Tim sort의 등장 2002년 소프트웨어 엔지니어 Tim Peters에 의하여 Tim sort가 등장했다. 이 정렬 알고리즘은 Insertion sort와 Merge sort를 결합하여 만든 정렬이다. 실생활 데이터의 특성을 고려하여 더욱 빠르게 고안된 이 알고리즘은 최선의 시간 복잡도는 \(O(n)\), 평균은 \(O(n\log n)\), 최악의 경우 시간 복잡도는 \(O(n\log n)\)이다. Tim sort는 안정적인 두 정렬 방법을 결합했기에 안정적이며, 추가 메모리는 .. 2022. 2. 17. 합병 정렬(Merge Sort) [Python / 파이썬] -목차- 1. 합병 정렬(Merge Sort) 2. 합병 정렬의 시간 복잡도 3. 합병 정렬의 특성 1. 합병 정렬(Merge Sort) 합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 합병 정렬은 아래와 같은 알고리즘으로 동작한다. 배열을 원소가 하나밖에 남지 않을 때까지 계속 둘로 쪼갠다. 더 이상 쪼갤 수 없는 각각의 배열을 합병하며 정렬한다 이때 크기 순으로 재배열하며 힙병이 이루어진다. 이해를 돕기 위해 예제를 통해 자세한 동작 원리를 알아보자. 예를 들어, 아래와 같이 1부터 8까지 총 8개의 숫자가 들어있는 배열에 있다고 가정해보자. [6, 5, .. 2022. 2. 17. Hash Table 1. Hash Table이란 특정한 값을 Search 하는데 데이터 고유의 인덱스로 접근하게 되므로 average case에 대하여 Time Complexity 가 O(1)이 되는 것이다.(항상 O(1)이 아니고 average case에 대해서 O(1)인 것은 collision 때문이다.) 그래서 특별한 알고리즘을 이용하여 저장할 데이터와 연관된 고유한 숫자를 만들어 낸 뒤 이를 인덱스로 사용한다. 특정 데이터가 저장되는 인덱스는 그 데이터만의 고유한 위치이기 때문에, 삽입 연산 시 다른 데이터의 사이에 끼어들거나, 삭제 시 다른 데이터로 채울 필요가 없으므로 연산에서 추가적인 비용이 없도록 만들어진 구조이다. 2. Hash Function 위에서 언급한 '특별한 알고리즘'을 hash method 또는 .. 2022. 2. 14. 이전 1 2 3 4 다음
