목록ALL (158)
Nagie's DevStory
std::priority_queue는 C++ 표준 라이브러리(STL)에서 제공하는 우선순위 큐를 구현한 컨테이너 어댑터이며, 내부적으로 힙(Heap) 자료구조를 사용하여 구현되어 있고 헤더 파일에 정의되어 있다. 우선순위 큐는 각 요소가 우선순위를 가지며, 가장 높은 우선순위를 가진 요소가 가장 먼저 나오는 특성이 있다. 그리고 std::priority_queue는 std::queue와 유사하지만, 요소들이 큐에 들어갈 때마다 자동으로 정렬되어 우선순위가 높은 요소가 먼저 나오게 되며, 기본적으로 최대 힙(Max Heap)이 사용되어 요소들이 내림차순으로 정렬된다. 즉, 가장 큰 요소가 가장 앞에 위치한다는 말이다. 특징 1. 힙 기반 구현 : 내부적으로 이진 힙(Binary Heap) 자료구조를 사용하..
우선순위 큐(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..