목록전체 글 (158)
Nagie's DevStory
std::multiset은 C++ 표준 라이브러리(STL)에서 제공하는 중복된 값을 허용하는 정렬된 집합을 나타내는 컨테이너다. 헤더 파일에 정의되어 있으며 내부적으로 레드-블랙 트리와 같은 자료 구조를 기반으로 구현되어 있다. 특징 1. 중복된 요소 허용 : 각 요소는 키만 저장하며, 중복된 키를 허용한다. 즉 동일한 값을 여러 개 저장할 수 있다. 2. 자동 정렬 : 오름차순으로 요소들이 정렬되어 저장된다. 3. 이진 탐색 트리 기반 : 대부분의 구현에서는 이진 탐색 트리나 비슷한 데이터 구조를 기반으로 하여 빠른 삽입, 삭제, 검색을 지원한다. (이진 탐색 트리의 일종인 레드-블랙 트리로 구현되어 있음) 4. 반복자(iterator) 제공 : begin()과 end()를 통해 반복자를 얻을 수 있어..
std::set은 C++ 표준 라이브러리(STL)에서 제공하는 중복을 허용하지 않는 정렬된 집합을 나타내는 컨테이너다. 헤더 파일에 정의되어 있으며 내부적으로 레드-블랙 트리와 같은 자료 구조를 기반으로 구현되어 있다. 특징 1. 중복을 허용하지 않음 : 각 요소는 유일해야 하며, 중복된 값을 저장하지 않는다. 2. 자동 정렬 : 오름차순으로 요소들이 정렬되어 저장된다. 3. 이진 탐색 트리 기반 : 대부분의 구현에서는 이진 탐색 트리나 비슷한 데이터 구조를 기반으로 하여 빠른 삽입, 삭제, 검색을 지원한다. (이진 탐색 트리의 일종인 레드-블랙 트리로 구현되어 있음) 4. 반복자(iterator) 제공 : begin()과 end()를 통해 반복자를 얻을 수 있어서 반복문을 통해 접근할 수 있다. 5. ..
이진 탐색 트리(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. 시간 복잡도 : 최악의 경우, 탐색하려는 원소가 배열의 맨 끝에 있거나 원소가 존재하지 않는 경우 전체 배..