Nagie's DevStory

우선순위 큐(Priority Queue)는 각 원소에 우선순위를 부여하고, 이 우선순위에 따라 원소들을 처리하는 자료구조다. 즉, 가장 높은 우선순위를 가진 원소가 다른 원소보다 먼저 처리된다. 그리고 이번 게시글에선 기존처럼 장단점을 나눠 정리하는 것이 아닌 구현법과 활용법을 작성할 예정이다. #include #include class MinHeap { private: std::vector heap; void heapify_up(int index) { int parent = (index - 1) / 2; while (index > 0 && heap[index].first < heap[parent].first) { std::swap(heap[index], heap[parent]); index = pare..

힙(Heap)은 특정한 규칙에 따라 정렬된 완전 이진 트리(Complete Binary Tree)의 형태를 가지는 자료 구조다. 힙은 주로 최댓값이나 최솟값을 빠르게 찾기 위한 목적으로 사용되며, 부모 노드의 키 값은 항상 자식 노드의 키 값보다 크거나 같은 "최대 힙 속성"과 부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같은 "최소 힙 속성" 즉 2가지 속성을 갖고 있다. #pragma once #include #include class MaxHeap { private: std::vector vec; int parent(int i) { return i / 2; } int left(int i) { return 2 * i; } int right(int i) { return 2 * i + 1; ..

이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식 노드를 가지며, 각 노드의 왼쪽 서브 트리는 해당 노드보다 작은 값, 오른쪽 서브 트리는 해당 노드보다 큰 값으로 구성된 이진 트리이다. 이 특성 덕에 효율적인 탐색과 정렬된 데이터 저장이라는 장점을 가지고 있지만, 데이터의 균형을 유지하는 추가적인 작업이 필요하며 최악의 경우 성능이 저하되는 단점을 가지고 있다. 위와 같은 단점을 해결한 균형 트리는 대표적으로 AVL 트리, 레드-블랙 트리, B 트리, 스플레이 트리 등이 있다. #pragma once #include struct Node { int data; Node* left; Node* right; Node(int d) : data(d), left(null..

아래는 C++로 구현된 이진 트리(Binary Tree)의 소스 코드다. 연결리스트처럼 노드 개념이 존재하고 자료의 계층 구조를 나타낼 때 사용하며 뿌리(root), 가지(branch), 잎(leaves) 등의 개념을 사용하여 데이터를 구성한다. //Tree.h 내용 #pragma once #include #include struct Node { char data; Node* left; Node* right; Node(char d) :data(d),left(nullptr), right(nullptr){} }; void preorder(Node* node) { //전위 순회 if (node) { std::cout data left); preorder(node->right); } } void inorder(..

아래의 코드는 C++로 구현된 덱(Deque)이다. std::deque가 동작하는 결과를 보고 std::vector를 사용해 흉내만 내봤다. #pragma once #include template class MyDeque { private: std::vector data; public: void pushFront(const T& item) { data.insert(data.begin(), item); } void pushBack(const T& item) { data.push_back(item); } void popFront() { if (!isEmpty()) { data.erase(data.begin()); } } void popBack() { if (!isEmpty()) { data.pop_back(..