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

이진 탐색(Binary Search)은 탐색 범위를 반으로 나누어 원하는 값을 찾아내는 알고리즘이다. 주로 정렬된 배열 또는 리스트에서 사용되며, 원하는 값과 중간 위치의 값을 비교해 탐색 범위를 계속해서 반으로 나누어 가면서 목푯값을 찾아낸다. 분할 정복(divide and conquer) 기법을 기반으로 하며, 각 단계에서 탐색 범위를 반으로 줄여나가기 때문에 효율적인 알고리즘 중 하나이다. template bool binary_search(const std::vector& data, T target) { int lower = 0; int upper = data.size() - 1; while (lower

선형 탐색(Linear Search)은 배열이나 리스트와 같은 자료 구조에서 특정 원소를 찾기 위해 처음부터 끝까지 순차적으로 탐색하는 알고리즘을 말하며, 검색할 요소들이 정렬되어 있지 않은 경우에도 적용할 수 있다. template bool linear_search(const std::vector& data, T target) { for (const T& element : data) { if (element == target) { return true; } } return false; } 특징 1. 순차적 탐색 : 시작부터 끝까지 각 원소를 비교하면서 찾고자 하는 값을 찾을 때까지 진행한다. 2. 시간 복잡도 : 최악의 경우, 탐색하려는 원소가 배열의 맨 끝에 있거나 원소가 존재하지 않는 경우 전체 배..