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..
CS Study/CLRS (자료구조 | 알고리즘)
0. Review- 6-1 에서 우리는 Heap을 알아가는 동안 Max-Heap에 대해서 알아보았다.- 이번 챕터에서는 Max-Heap을 유지하게 해주는 Max-Heapify 에 대해서 알아볼 것이다. 1. Max-Heapify- Max-Heapify 절차는 최댓값 힙 속성을 유지한다.- 입력값은 배열 A, 그리고 배열의 인덱스 i를 받는다.- Max-Heapify는 LEFT(i), RIGHT(i)로 시작하는 Heap들이 이미 Max Heap이라는 것을 가정한다. - 하지만 A[i]가 자식노드보다 작을 경우 Max-Heap을 만족하지 않는다.- 그래서 A[i]를 아래에 있는 노드로 계속 흘려보내면서 Max-Heap을 만족하게 한다.- 다음 그림은 Max-Heapify의 동작을 보여준다. - (a)상황을 ..
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- 자료구조나 알고리즘은 실생활에 적용되는 경우가 많은데 그 중 고용문제에 대해 다뤄볼까한다.- 당신이 새로원 직원을 고용해야한다고 가정해보자. - 이전의 고용했던 시도들은 성공적이지 못해서 고용 대행사를 이용하기로 결정하였다.- 고용 대행사는 매일 한 명의 후보자를 보내고, 당신은 그 후보자를 면접을 진행한 뒤 그 사람을 고용할 지에 대한 여부를 결정한다.- 즉, 기존에 있던 직원을 해고하고, 더 유능한 직원을 뽑고자 하는 것이다. 2. 직원 고용- 이를 코드로 나타낸다면 다음과 같을 것이다.... 챕터 5는 투자하면서 정리하기엔 의미가 없을거라 판단하여 생략하고자 한다.
