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

std::multimap은 C++ 표준 라이브러리(STL)에서 제공하는 중복된 키를 허용하는 연관 컨테이너이다. std::map과 유사하지만, std::multimap은 한 개의 키에 여러 개의 값을 저장할 수 있으며. 헤더 파일에 정의되어 있다. 특징 1. 중복된 키 허용 : std::map과는 다르게 동일한 키에 대해 여러 개의 값을 저장할 수 있다. 3. 자동 정렬 : 키에 대한 자동 정렬이 기본적으로 수행된다. 4. 검색 및 삽입 연산이 빠름 : 트리 기반이기 때문에 검색 및 삽입 연산이 빠르다. 5. 반복자(iterator) 제공 : begin()과 end()를 통해 반복자를 얻을 수 있어서 반복문을 통해 접근할 수 있다. 사용법 #include #include int main() { std::..

std::map은 C++ 표준 라이브러리에서 제공하는 키-값(Key-Value)을 쌍으로 저장하는 연관 컨테이너다. 각 키는 유일해야 하며, 키를 기반으로 값을 검색하고 관리한다. std::map도 std::set과 같이 내부적으로 레드-블랙 트리와 같은 자료 구조를 기반으로 구현되어 있으며, 헤더 파일에 정의되어 있다. 특징 1. 키-값을 쌍으로 저장 : 각 요소는 키와 값으로 이루어져 있으며, 특정 키에 대응하는 값을 저장한다. 2. 유일한 키 : 각 키는 유일해야 하며, 중복된 키를 허용하지 않는다. 3. 자동 정렬 : 키에 대한 자동 정렬이 기본적으로 수행된다. 4. 검색 및 삽입 연산이 빠름 : 트리 기반이기 때문에 검색 및 삽입 연산이 빠르다. 5. 반복자(iterator) 제공 : begin..

std::multiset은 C++ 표준 라이브러리(STL)에서 제공하는 중복된 값을 허용하는 정렬된 집합을 나타내는 컨테이너다. 헤더 파일에 정의되어 있으며 내부적으로 레드-블랙 트리와 같은 자료 구조를 기반으로 구현되어 있다. 특징 1. 중복된 요소 허용 : 각 요소는 키만 저장하며, 중복된 키를 허용한다. 즉 동일한 값을 여러 개 저장할 수 있다. 2. 자동 정렬 : 오름차순으로 요소들이 정렬되어 저장된다. 3. 이진 탐색 트리 기반 : 대부분의 구현에서는 이진 탐색 트리나 비슷한 데이터 구조를 기반으로 하여 빠른 삽입, 삭제, 검색을 지원한다. (이진 탐색 트리의 일종인 레드-블랙 트리로 구현되어 있음) 4. 반복자(iterator) 제공 : begin()과 end()를 통해 반복자를 얻을 수 있어..