알고리즘

0. Intro- 우리는 6-2, 6-3 에서 max_heapify()와 build_max_heap()을 구현해보았다.- 두 함수를 이용하여 배열을 정렬하는 알고리즘을 한번 구현해보자(Heapsort) 1. Heapsort?- 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법을 의미함- Heapsort의 알고리즘을 나타내면 다음과 같다. i) 정렬해야할 n개의 데이터들을 Max-Heap을 만든다.ii) root-node(최댓값을 가장 마지막 node와 바꾼다.iii) 그 후 heap에서 pop()을 한 후 queue에 enqueue한다.iv) 그 후 max_heapify()를 root_node에서 실행한다.v) ii)~iv)까지를 계속 반복한다. (heap이 empty가 될 때까지) - heaps..

0. Review- 이번 챕터에서는 Max-Heap을 만들기 위해 6-2에서 구현했던 max_heapify()를 이용하고자 한다.- 이를 leaf-node(자식이 없는 노드)부터 시작하여 root-node까지 거슬러 올라가 max_heapify()를 호출하면 된다.- 이때 leaf-node는 heap에서 다음과 같다. A[n//2 + 1: ] 까지에 해당한다. - leaf-node에서 max_heapify()를 호출하더라도 변함없기 때문에 구현할 코드에선 A[n//2] ~A[1]까지만 호출하는 것으로 구현하였다. 1. Code1.1. max_heapify()def max_heapify(arr,i): left_node = 2*i right_node = 2*i+1 if (left_no..

1. Heaps?- 우선 힙을 저장하는 자료구조는 배열이다.- 일반적으로 이진 트리(Binary Tree)로 구현되는 완전 이진 트리의 형태다.- 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.- 구현을 쉽게 하기 위해 0인 인덱스는 사용하지 않고 1부터 사용된다.- 그림으로 나타내면 다음과 같다. (트리의 높이는 log(n)이 된다.)  2. 힙에서의 부모노드와 자식노드의 관계i번째 노드- 부모 노드 인덱스 : i//2- 왼쪽 자식 노드 인덱스 : 2*i- 오른쪽 자식 노드 인덱스 : 2*i + 13. Max Heap- 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 - 즉, 다음을 만족하는 Heap을 의미한다. A[parent(i)] >= A..

1. Introduction- [4-5] 에선 마스터 정리에 대한 공식을 알아 봤다면, 이 공식이 어떻게 나왔는지 증명을 통해서 알아보자. 2. Proof- 1) T(n)을 시그마를 이용하여 정리한다. - 2) c   - 3) c = log_b(a) 일 때, - 4) c > log_b(a) 일 때,