본문 바로가기

분류 전체보기

 (308)
[알고리즘] 해시 테이블 map vs hash_map map : 레드 블랙 트리 추가, 탐색, 삭제가 logN의 시간복잡도를 가짐 hash map(unordered_map) 추가, 탐색, 삭제가 1의 시간복잡도를 가짐 hash_map은 메모리를 내주고 속도를 취한다. 예를 들면 유저의 수대로 메모리에 공간을 만들어 거기에 데이터를 집어넣는 것이다. 이러한 방식을 테이블이라고 하고, 키를 알면 데이터를 바로 알아낼 수 있다. 그리고 해시는 보안 때문에 데이터를 임의의 값으로 바꾸는 것이다. 간혹 해시(키)값이 중복해서 충돌하는 문제가 발생하는데, 해결방법은 선형 조사법, 이차 조사법이 있다. 선형 조사법: 해시 키에 충돌하지 않을 때까지 1씩 더함 이차 조사법: 더 분산된 키를 넣는 방법으로 1^2, 2^2씩 더함 MMORPG처럼..
[알고리즘] 힙 정렬, 병합 정렬 힙 정렬 힙 정렬은 힙의 특성을 이용한 정렬이다. 우선순위 큐가 힙의 특성을 이용하기 때문에 우선순위 큐를 사용하여 구현할 수 있다. void HeapSort(vector& v) { priority_queue pq; // O(NlogN) for (int num : v) pq.push(num); v.clear(); // O(NlogN) while (pq.empty() == false) { v.push_back(pq.top()); pq.pop(); } } 우선순위 큐에 push할 때 시간복잡도는 logN이고 그걸 N번 반복하므로 시간복잡도는 NlogN이다. pop하는 것도 logN이고 우선순위큐가 비워질 때까지 N번 반복하브로 마찬가지로 NlogN이다. 병합정렬 병합정렬은 분할 정복을 이용하는데 분할, 정복..
[알고리즘] 레드 블랙 트리 - 2.삭제 레드 블랙 트리에서 삭제할 때 빨간색 노드일 때는 문제가 없지만 검정색 노드일 경우 문제가 발생한다. 검정색 노드를 삭제하면 레드 블랙 트리의 원칙인 어떤 노드로부터 그에 속한 하위 리프 노드에 도달하는 경로에는 모두 같은 개수의 블랙 노드를 만난다는 원칙에 위배되기 때문이다. 검정색 노드를 삭제하고 그 자리의 nil 노드를 black으로 설정하는데 nil 노드는 검정색 노드이므로 이를 Double Black 상태라고 한다. Double Black 상태에서는 폭탄 돌리기를 시작하는데 Red 노드를 만날 때 까지 이리저리 건네준다. 그래서 폭탄 돌리기하면서 분기로 나누어진다. Case 1. 루트 노드가 Double Black일 때 삭제할 검정색 노드를 그냥 삭제하면 된다. Case 2. Double Bla..
[알고리즘] 레드 블랙 트리 - 1.삽입 이진 탐색 트리는 문제점이 있는데 데이터가 한쪽에 편향될 경우 탐색 효율이 연결 리스트와 별 다를 것 없어진다는 것이다. 그래서 데이터 편향을 방지하는 트리가 레드 블랙 트리이다. 레드블랙 트리는 다음과 같은 규칙을 가진다. 노드는 레드 혹은 블랙 중의 하나이다. 루트 노드는 블랙이다. 모든 리프 노드들(NIL)은 블랙이다. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다) 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. 레드 블랙트리의 삽입 방식은 이진 탐색트리와 동일하지만 삽입하고나서 레드 블랙 트리의 규칙에 맞춰..
[알고리즘] 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리는 부모 노드가 자식 노드보다 크다는 점은 힙 트리와 같다. 하지만 부모노드 기준 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값이어야 한다. 그래서 값을 찾을 때 한단계 내려갈 때마다 데이터 절반에 해당하는 서브트리를 제외할 수 있어서 log n의 시간 복잡도를 가지는 장점이 있다. void BinarySearchTree::Print_Inorder(Node* node) { // 전위 순회 (preorder traverse) // 중위 순회 (inorder) // 후위 순회 (postorder) if (node == nullptr) return; // 전위 : [중]이 앞에 온다 // 중위 : [중]이 중간에 온다 // 후위 : [중]이 마지막에 온다 cout key left..
[알고리즘] A* 길찾기 알고리즘 A*는 점수를 매겨 길을 찾는다. F = G + H F : 최종 점수(작을수록 좋음, 경로에 따라 달라짐) G : 시작점에서 해당 좌표까지 이동하는데 드는 비용(작을수록 좋음, 경로에 따라 달라짐) H : 목적지에서 얼마나 가까운지(작을수록 좋음, 고정) // ClosedList // close[y][x] -> (y, x)에 방문을 했는지 여부 vector closed(size, vector(size, false)); // best[y][x] -> 지금까지 (y, x)에 대한 가장 좋은 비용 (작을 수록 좋음) vector best(size, vector(size, INT32_MAX)); // 부모 추적 용도 map parent; // OpenList priority_queue pq; 먼저 방문했는지 여..
[알고리즘] 힙 트리를 이용한 우선순위 큐 우선순위 큐는 큐처럼 선입선출이 아닌 값이 큰 순서대로 pop한다. 우선순위 큐는 힙 트리를 이용해 구현할 수 있고 힙 트리는 데이터가 꽉 차 있는 형태이기 때문에 데이터를 배열로 표현할 수 있다. void push(const T& value) { heap.push_back(value); int now = static_cast(heap.size()) - 1; while (now > 0) { int parent = (now - 1) / 2; if (heap[parent] < heap[now]) { ::swap(heap[parent], heap[now]); now = parent; } else break; } } 힙 트리를 배열로 표현할 때 i 번째 노드의 부모는 (i-1)/2 이므로 이를 이용해 현재 노드..
[알고리즘] 힙 트리 힙 트리는 자식 노드가 최대 두개인 이진 트리이다. 힙 트리의 특징은 다음과 같다. 1. 부모 노드의 값이 자식 노드 값보다 크다. 2.마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있고(완전 이진 트리) 마지막 레벨의 노드는 왼쪽부터 순서대로 채운다. 그래서 노드 개수를 알면 트리 구조를 확정할 수 있다. 배열을 이용해 힙 구조를 표현할 수 있는데, i번 노드의 왼쪽 자식은 [2*i + 1] 번 노드, i번 노드의 오른쪽 자식은 [2*i + 2] 번 노드, i번 노드의 부모는 [(i - 1)/2] 번 노드 3. 새로운 값을 추가할 때는 마지막 레벨에 추가한 후 부모와 도장 깨기를 한다. 도장 깨기란 부모 노드보다 값이 클 경우 부모와 자식을 교체하는 것이다. 4. 트리의 최대 값을 꺼내는 것은 루트 노..

티스토리툴바