Crat

6-2. 최소 신장 트리(Minimum Spanning Tree), 크루스칼 알고리즘(Kruskal Algorithm)

1. 최소 신장 트리(최소 스패닝 트리 ; Minimum Spanning Tree) 최소한의 간선을 이용하여 모든 정점을 연결한 트리. (1) 순환이 발생하면 안됨 ex) 0 -> 1 -> 2 -> 0 -> 1 ... (2) 정점이 N개이면 간선은 N-1개 2. 크루스칼 알고리즘 (Kruskal MST Algorithm) 탐욕적인(greedy) 방법을 이용함. -> 지금 순간에 최적인 답을 선택하여 결과를 도출 - 원리 (1) 코스트가 가장 낮은 간선들을 선택 (2) 코스트가 가장 낮은 다른 간선을 연결 (3) 그 다음으로 코스트가 낮은 간선을 연결 반복 단, 연결 사이에 순환이 발생하면 안됨(MST의 조건에 미달) - 순환을 판단하는 방법 연결이 완료된 정점들을 그룹으로 관리한다. 이 때 같은 그룹내에..

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 (..

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) 새로운 노드는 레드..

4-2. 이진 탐색 트리(BST ; Binary Search Tree)

1. 기본 구조 (1) 트리 형태로 출력하기 트리 형태로 출력하기 위해 콘솔 창의 커서 위치를 지정할 수 있는 함수를 사용한다. #include using namespace std; void SetCursorPosition(int x, int y) { HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE); COORD pos = { static_cast(x), static_cast(y) }; ::SetConsoleCursorPosition(output, pos); } BinarySearchTree.cpp SetCursorPosition 함수에 x와 y값을 입력하여 출력되는 값의 위치를 조정할 수 있다. (2) 노드 struct Node { Node* left = null..

4-1. 이진 탐색(Binary Search)

1. 이진 탐색(Binary Search) 배열에 데이터가 정렬되어 있는 상황을 보자. v = { 1, 8, 15, 23, 32, 44, 56, 63, 81, 91 }; 여기에서 82라는 숫자가 배열에 있는지 찾을 수 있을까? 이진 탐색을 이용하면 반복자를 이용하여 O( N )의 시간 복잡도로 찾는 방법보다 더 빠른 탐색이 가능하다. 대략 중간에 위치한 인덱스를 이용하여 그 인덱스의 데이터와 82를 비교하여 더 작으면 더 작은 절반을 날리는 식으로 탐색을 수행한다. (시간 복잡도 = O ( log N ) ) 2. 이진 탐색 구현 - 이미 정렬된 배열 탐색하기 void BinarySearch(int N) { int left = 0; int right = (int)numbers.size() - 1; bool..