Crat

6-1. 상호 배타적 집합 (Disjoint Set)

최소 스패닝 트리를 공부하기 전에, 최소 스패닝 트리에 적용되는 서로소 집합에 대해서 공부한다. 1. 상호 배타적 집합(서로소 집합) ; Disjoint Set - 공통 원소(혹은 공통 부분 집합)를 가지지 않는 집합, 교집합이 없는 집합들. ex) { 1, 2, 3 } 과 { 4, 5, 6 } 은 서로소 집합이다. (1) 유니온-파인드(Union-Find) 알고리즘 - 유니온 (Union) : 두 개의 서로소 집합을 하나로 합침. - 파인드 (Find) : 주어진 원소를 가지는 집합을 찾음. 주어진 원소의 루트 노드를 찾는 것이 목표. 2. 트리 구조를 이용한 표현 class NaiveDisjointSet { public: NaiveDisjointSet(int n) : _parent(n) { for (..

5-4. 해시 테이블(Hash Table)

0. map vs hash_map (std::unordered_map) (1) map ( C#의 dictionary와는 다름 ) - 균형 이진 트리의 트리 구조, 레드-블랙 트리로 구성되어 있음 - 키를 기준으로 자동으로 정렬해서 저장 - 시간 복잡도 : O( log N ) (2) hash_map (std::unordered_map, C#의 dictionary) - 메모리를 대가로 속도를 이점으로 가져감 - 삽입 순서에 따라서 저장 - 해시 충돌이 없으면 속도가 map에 비해 굉장히 빠름 - 시간 복잡도 : 데이터의 추가, 탐색, 삭제가 상수의 시간 복잡도를 가짐 => O(1) 1. 해시 테이블 ; unordered_map 키-값 쌍으로 이루어져 있으므로 특정 값에 접근하려면 키만 알면 됨. 그러나 키-..

5-3. 퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick Sort)의 원리 (1) 인덱스 지정 - 배열의 첫 값을 pivot(피벗)으로 지정 - 그 다음 값을 시작위치인 low로 지정 - 배열의 마지막 값을 high로 지정 (2) 인덱스 이동 - pivot >= arr[low] 일 때까지 low 인덱스를 1씩 증가시킴 - pivot low보다 커질 때 알고리즘을 종료 - arr[pivot] 과 arr[high] 교체 위의 알고리즘을 통해 피벗을 기준으로 좌측은 피벗 값보다 작게, 피벗을 기준으로 우측은 피벗 값보다 크게 정렬된다. 2. 퀵 정렬 구현 int Partition(vector& v, int left, int right) { int pivot = v[left]; int low = left + 1; int high = right..

5-2. 힙 정렬, 병합 정렬

1. 힙 정렬(Heap Sort) 힙의 특성을 이용한 정렬. void HeapSort(vector& v) { priority_queue pq; // 우선순위 큐를 내림차순으로 정렬 for (int num : v) // 벡터 v의 모든 값을 우선순위 큐에 대입 pq.push(num); v.clear();// 벡터 v를 비움 while (pq.empty() == false) // 우선순위 큐가 빌 때 까지 { v.push_back(pq.top()); // 벡터 v에 우선순위 큐의 값을 작은 순서대로 집어넣음 pq.pop();// 우선순위 큐의 맨 위 데이터 제거 } } 우선순위 큐는 힙 구조로 되어있다. 우선순위 큐를 내림차순으로 정렬되어 있기 때문에 가장 작은 값이 우선순위 큐의 Top에 위치한다. 우선순..

5-1. 버블 정렬, 선택 정렬, 삽입 정렬

상대적으로 비효율적으로 동작하는 기본 정렬들이다. 1. 버블 정렬(Bubble Sort) 바로 옆의 원소와 비교하며 큰 수를 마지막에 오게 한다. 루프 한 번마다 큰 수를 하나씩 정렬한다. void BubbleSort(vector& v) { for (int i = 0; i v[j + 1]) { temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; } } } } 인덱스는 0부터 시작하기 때문에, 인덱스 4번까지 정렬을 하겠다면 벡터의 사이즈보다 1 작은 만큼 정렬해야 한다. 또..

4-5. 레드-블랙 트리(RBT ; Red-Black Tree) - (3) 데이터 삭제 구현

1. 기본 구성 (1) 콘솔 창에서 커서의 깜빡임을 감추기 void ShowConsoleCursor(bool flag) { HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE); CONSOLE_CURSOR_INFO cursorInfo; ::GetConsoleCursorInfo(output, &cursorInfo); cursorInfo.bVisible = flag; ::SetConsoleCursorInfo(output, &cursorInfo); } (2) Print 함수에서 매번 출력값을 지우면서 Print 하기 void BinarySearchTree::Print() { ::system("cls"); ShowConsoleCursor(false); Print(_root, ..

4-4. 레드-블랙 트리(RBT ; Red-Black Tree) - (2) 데이터 삭제

1. 데이터 삭제 일반적으로 이진 탐색 트리와 동일하게 작동한다. 하지만 색상을 변경하는 부분이 추가된다. (1) 삭제할 노드가 Red인 경우 BST의 삭제 알고리즘으로 해당 노드를 제거하면 된다. (2) 삭제할 노드가 Black인 경우 어떤 노드로부터 하위 리프 노드에 도달하는 모든 경로에는 같은 개수의 블랙 노드를 만나야 한다. (왼쪽 : 10 - 5 - NIL, 2개의 Black 노드 / 오른쪽 : 10 - 20 - NIL, 1개의 블랙노드) 따라서 BST의 삭제 알고리즘 이후, 같은 개수의 블랙 노드를 만나게 하기 위하여 NIL 노드를 두 개 가지고 있도록(중첩시켜 ; Double Black) 만들 수 있다. 그리고 중첩된 black 하나를 하나씩 위로 올리면 된다. 2. 삭제할 노드가 Black..

4-3. 레드-블랙 트리(RBT ; Red-Black Tree) - (1)

0. 이진 탐색 트리의 문제점 이진 탐색 트리는 균형이 한 쪽으로 무너지면 속도에서의 이점이 사라지게 된다. 레드-블랙 트리는 균형을 맞추기 위해 색 변경, 노드 회전(부모 - 자식 위치 변경)의 과정을 거친다. 1. 레드-블랙 트리(Red-Black Tree)의 특징 이진 탐색 트리를 기반으로 한다. (1) 모든 노드는 블랙 또는 레드 중 하나이다. (2) 루트 노드는 블랙이다. (3) 모든 리프 노드는 블랙이다. (4) 레드 노드의 자식 노드 양쪽은 언제나 블랙이다. (레드 노드는 연속적으로 있을 수 없다 -> 레드 노드의 부모와 자식은 블랙이어야 한다) (5) 어떤 노드에서 하위 리프 노드로 가는 모든 경로에는 (리프 노드를 제외하고) 모두 같은 개수의 블랙 노드가 있다. (6) 새로운 노드는 레드..