1. What is Priority Queue(우선순위 큐란)?Queue(FIFO) 와 유사하다. 여기서 각 요소에 우선 순위가 있다는 것이 바로 Priority Queue라 한다. 2. How to implement a priority queue (어떻게 우선순위 큐를 구성할 것인가)?Heap-based implementation (우리는 이 방식을 쓸 것이다.)우선순위 큐 구성 방식특징a unsorted array/linked list요소를 마지막 위치에 삽입한다.우선 순위가 가장 높은 요소를 순차적으로 검색한다.임의 요소 삽입: O(1) / 최댓값 검색: O(n) / 최댓값 삭제 : O(n)a sorted array/linked list내림차순으로 요소를 삽입할 수 있다. 또한 첫번째 요소를 간단히..
1. Hash란?임의의 크기의 값을 고정된 크기의 값으로 매핑하는 데 이때 해시 함수를 사용한다.key 와 values 를 가진다.검색 속도를 O(1)으로 만들기 위해 사용된다.2. 좋은 Hash Function은?해시 함수는 원소들이 균일하게 분포될 수 있을 만큼 충분히 골고루 분포되어야 한다.– 해시 함수는 편향되지 않아야 한다.– 요소에 모든 비트를 사용해야 한다 범용 해시 함수– 𝑏 버킷이 있는 경우 ℎ (𝑥) = 𝑖 확률은 모든 버킷에 대해 1/𝑏 이다.(이러한 확률을 가지고 있어야 굿)– 요소 𝑥는 1/𝑏 확률로 모든 버킷 𝑖에 넣을 수 있다.Hash Function으로는 Mid-square, Division, and Folding을 사용한다. 2.1. Hash Function 종..
1. Sorting 이란?배열에 데이터를 담게 되면, 가끔은 데이터를 정렬하고 싶을 때가 있을 것이다. 당연히 정렬된 데이터가 그렇지 않은 데이터에 비해 보기도 편하고, 상황에 따라 다루기도 편하기 때문이다.이처럼 정렬의 중요성은 높기 때문에, 수많은 정렬 알고리즘이 되었다.우리는 일상적인 정렬 알고리즘에서 시작하여, 개선된 시간의 정렬 알고리즘까지 공부할 것이다.https://visualgo.net/en/sorting 에서 직관적으로 이해할 수 있다. Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgoVisuAlgo is generously offered at no cost to the global Comput..
1. AVL Tree의 정의스스로 균형을 잡는 Binary Search TreeBalance(X) = -Height(LeftSubtree(X)) + Height(RightSubTree(X)) 2. AVL Tree의 예시3. RebalanceRotation과 더불어 AVL Tree의 핵심 중 하나이다. GetBalancingFactor 함수로 통해 Tree의 높낮이를 계산 후 불균형이라면 어느 부분에서 불균형인지 판단 후 회전을 진행한다. BSTNode* Rebalance(BSTNode* root) { int factor = GetBalancingFactor(root); if (factor left_child 1) { if (GetBalancingFactior((root)->right_chi..
1. Red-Black Tree1.1. Red-Black Tree란Binary Search Tree의 일종이다.Balance Tree의 일종이다.다음 조건을 만족하면 Red-Black Tree이다.– P1. 모든 노드는 빨간색 또는 검은색이다.– P2. 각 NULL 포인터는 검은색으로 간주된다.– P3. root는 검은색이다.– P4. 어떤 노드가 빨간색이면, 그 노드의 두 자식은 모두 검은색입니다– P5. root에서 어떤 leaf 노드로 가는 모든 경로는 동일한 수의 black 노드를 포함한다.1.2. Red-Black Tree 예시1.3. Red-Black Tree 의 기능1.3.1 SearchingBinary Search Tree랑 완전 같다.// Recursive versionBSTNode* S..
