간격 힙(interval heap)에서 최소 요소는 항상 루트 노드의 왼쪽에 위치합니다. 따라서 최솟값 제거(removeMin) 연산은 루트의 왼쪽 요소를 반환하는 것에서 시작되며, 제거 후 힙의 구조적 조건을 유지하기 위해 일련의 재배치 과정이 필요합니다.기본 제거 절차간격 힙에서 최소 요소는 루트 노드의 왼쪽에 있는 요소입니다. 이 요소를 제거하고 반환합니다.루트 노드 왼쪽에 생긴 빈자리를 채우기 위해, 마지막 노드에서 하나의 요소를 꺼내 다시 루트 노드에 삽입합니다.삽입된 요소는 하위 노드들의 왼쪽 요소들과 순차적으로 비교되며

간격 힙(interval heap)은 각 노드가 두 개의 원소를 저장하는 임베디드 min-max 힙(embedded min-max heap)과 동일한 자료구조입니다. 간격 힙은 완전 이진 트리(complete binary tree)로 정의되며, 다음과 같은 성질을 만족해야 합니다. 왼쪽 원소는 오른쪽 원소보다 작거나 같습니다. 두 원소는 하나의 닫힌 구간(closed interval)을 정의합니다. 루트를 제외한 모든 노드가 나타내는 구간은 부모 노드 구간의 부분 구간(sub-interval)입니다. 왼쪽에 위치한 원소들은 최소

간격 힙(Interval Heap)이란?양단 우선순위 큐(Double-Ended Priority Queue, DEPQ), 흔히 간격 힙(interval heap)이라고 불리는 자료구조는 최소 우선순위 요소와 최대 우선순위 요소를 모두 효율적으로 조회하고 삭제할 수 있는 힙 기반 구조입니다. 일반적인 최소 힙이나 최대 힙과 달리, 양쪽 끝에서 동시에 우선순위를 다룰 수 있다는 점이 가장 큰 특징입니다.간격 힙에서 지원하는 대표적인 연산은 다음과 같습니다.간격 힙의 주요 연산isEmpty()DEPQ가 비어 있는지 확인하는 함수로, 큐가

딥스(Deap)는 루트(root) 노드에 어떠한 원소나 키 값도 저장하지 않는 특수한 형태의 데이터 구조입니다. 이 구조는 다음과 같은 규칙에 따라 구성됩니다.딥스의 기본 규칙루트 노드에는 원소가 존재하지 않으며, 항상 비어 있습니다.딥스의 왼쪽 서브트리(left subtree)는 최소 힙(min heap) 역할을 수행합니다.딥스의 오른쪽 서브트리(right subtree)는 최대 힙(max heap) 역할을 수행합니다.이러한 구조적 특징 덕분에 딥스는 아래의 명제를 수학적으로 보장할 수 있습니다.핵심 성질어떤 노드의 왼쪽 서브트리

최소-최대 힙(Min-Max Heap)은 최소(min) 레벨과 최대(max) 레벨이 번갈아 나타나는 완전 이진 트리(complete binary tree)로 정의됩니다. 이때 짝수 레벨은 0, 2, 4처럼 최소 레벨을 의미하고, 홀수 레벨은 1, 3, 5처럼 최대 레벨을 의미합니다.이 글에서는 편의상 루트(root) 요소가 첫 번째 레벨, 즉 레벨 0에 위치한다고 가정합니다.최소-최대 힙의 주요 특징최소-최대 힙의 각 노드는 데이터 멤버(일반적으로 키(key)라고 함)를 가지며, 이 값은 해당 노드가 힙 내에서 어떤 순서를 갖는지

Deap에 요소 삽입하기Deap(Double-Ended Heap, 더블 엔디드 힙)은 최솟값과 최댓값을 모두 효율적으로 관리할 수 있는 힙 기반 자료구조입니다. Deap에 새로운 요소를 삽입하려면 먼저 최솟값과 최댓값의 위치를 계산하는 절차가 필요합니다.최솟값 및 최댓값 계산 절차Deap에서 특정 위치 m을 기준으로 대응되는 최솟값과 최댓값의 위치를 구하는 절차는 다음과 같습니다.min_value(m): Deap에서 최솟값의 위치를 계산합니다.return m − 2log₂(m−1)max_value(m): Deap에서 최댓값의 위치를

Deap에서 최소 요소 삭제 개요이번 장에서는 Deap(더블엔디드 힙) 자료구조에서 최솟값을 삭제하는 기법에 대해 알아보겠습니다. Deap의 삭제 연산은 트리의 루트에 위치한 최솟값을 제거하는 것을 목표로 합니다.Deap은 완전 이진 트리 형태를 유지하므로 트리의 높이는 항상 log n입니다. 따라서 삭제 연산 역시 O(log n)의 시간 복잡도로 수행됩니다.삭제 연산의 동작 원리Deap에서 삭제가 일어나는 과정은 다음과 같습니다.1단계: 먼저 배열에 저장된 요소의 개수(m)를 확인합니다. m이 2보다 작다면 삭제할 요소가 없으므로

듀얼 힙(Dual Heap)노드 aNode를 PQ에서 제거하는 remove(aNode) 연산을 효율적으로 지원하는 단일 방향 우선순위 큐(PQ) 자료구조로부터, 효율적인 DEPQ(Double Ended Priority Queue, 양단 우선순위 큐) 자료구조를 만들어 내는 일반적인 방법들이 존재합니다. 이 중 가장 간단한 방법인 듀얼 구조(dual structure) 방식은 DEPQ의 모든 원소에 대해 최소 PQ와 최대 PQ를 모두 유지하고, 동일한 원소를 담고 있는 최소 PQ와 최대 PQ의 노드 사이에 대응 포인터(correspo

이중 우선순위 큐(DEPQ)란?이중 우선순위 큐(Double Ended Priority Queue, DEPQ)는 최솟값과 최댓값을 모두 효율적으로 조회하고 삭제할 수 있는 자료구조입니다. 일반적인 단일 방향 우선순위 큐(PQ)는 최솟값 또는 최댓값 중 한쪽만 효율적으로 다룰 수 있지만, DEPQ는 양방향 연산을 지원합니다.단일 방향 우선순위 큐를 기반으로 효율적인 DEPQ 자료구조를 만드는 일반적인 방법들이 존재합니다. 단, 이때 사용되는 PQ는 remove(bNode) 연산도 효율적으로 제공해야 합니다. remove(bNode)는

대응(Correspondence) 기반 데이터 구조란?총 대응(total correspondence)과 리프 대응(leaf correspondence)은 양단 우선순위 큐(DEPQ, Double-Ended Priority Queue)를 구현하기 위한 보다 정교한 대응 기법입니다. 두 기법 모두 전체 원소의 절반은 최소 우선순위 큐(min PQ)에, 나머지 절반은 최대 우선순위 큐(max PQ)에 배치합니다. 만약 원소의 개수가 홀수라면, 하나의 원소는 버퍼에 저장되며 이 버퍼의 원소는 어느 쪽 PQ에도 속하지 않습니다.총 대응(To

병합 가능한 DEPQ(MDEPQ)란?병합 가능한 DEPQ(Meldable DEPQ, MDEPQ)는 기존의 양단 우선순위 큐(Double-Ended Priority Queue, DEPQ) 연산에 더해 meld(p, q) 연산을 추가로 지원하는 자료구조입니다. 이 연산은 두 개의 DEPQ인 p와 q를 하나의 DEPQ로 합치는 기능을 수행합니다. 병합 결과로 생성되는 큐에는 p와 q의 모든 원소가 포함됩니다. 단, meld 연산은 파괴적(destructive)으로 동작하기 때문에 병합이 완료된 후에는 p와 q가 독립적인 DEPQ로 남아

완전 해싱(Perfect Hashing)이란?완전 해싱은 임의의 n개 원소 집합을 그와 동일한 크기의 해시 테이블에 저장하고, 탐색(lookup) 연산을 상수 시간(O(1))에 수행할 수 있도록 보장하는 해싱 모델을 의미합니다. 이 기법은 프레드먼(Fredman), 코몰로시(Komlós), 세메레디(Szemerédi)가 1984년에 발명하고 체계적으로 논의했기 때문에, 세 사람의 이름을 딴 FKS 해싱이라는 별칭으로도 널리 알려져 있습니다.일반적인 해싱에서는 서로 다른 키가 같은 슬롯에 매핑되는 충돌(collision)이 발생할 수

정의동적 완벽 해싱(dynamic perfect hashing)은 해시 테이블 자료구조에서 발생하는 충돌(collision)을 해결하기 위한 프로그래밍 기법입니다. 이 방식은 어떤 경우에도 충돌 없이 상수 시간 내에 데이터에 접근할 수 있도록 보장하는 것이 특징입니다.활용 분야동적 완벽 해싱은 다른 해시 테이블 방식에 비해 더 많은 메모리를 소비하지만, 대규모 요소 집합을 대상으로 빠른 조회(query), 삽입(insertion), 삭제(deletion) 연산을 반복적으로 수행해야 하는 상황에서 특히 유용합니다. 따라서 성능이 메모

다중 선택 해싱(Multiple Choice Hashing)은 여러 개의 해시 함수를 사용한다는 점에서 그 이름이 유래했습니다.높은 수준에서 보면, 여러 해시 함수가 존재할 때 각 항목(item)은 여러 버킷(bucket)에 동시에 매핑되며, 알고리즘 설계자는 그중 어느 버킷에 항목을 저장할지 자유롭게 선택할 수 있습니다.흥미롭게도 이러한 선택의 자유 덕분에, 단일 해시 함수만 사용했을 때보다 훨씬 균형 잡힌 할당(allocation)을 달성하는 알고리즘을 설계할 수 있음이 밝혀졌습니다.본 글에서는 이러한 알고리즘의 핵심 아이디어와

블룸 필터(Bloom Filter)는 어떤 요소가 집합(set)에 존재하는지 여부를 빠르고 메모리 효율적으로 판별할 수 있도록 설계된 자료구조입니다.블룸 필터의 기본 개념블룸 필터는 확률적 자료구조(probabilistic data structure)에 속합니다. 이 자료구조를 활용하면 특정 요소가 집합에 속해 있는지, 혹은 속해 있지 않은지를 판별할 수 있습니다. 다만 확률적 자료구조의 특성상 반드시 없다는 보장은 가능하지만, 있다고 판정될 때는 아주 낮은 확률로 오탐(false positive)이 발생할 수 있다는 점을 기억해야

블룸 필터의 세 가지 성능 지표블룸 필터(Bloom Filter)에서는 서로 절충(trade-off) 관계에 있는 세 가지 성능 지표를 고려해야 합니다.연산(실행) 시간 — 해시 함수의 개수 k에 해당필터 크기 — 비트 수 m에 해당오류 확률 — 거짓 양성(false positive) 비율 f = (1 − p)k에 해당오류 허용과 네 가지 결과 유형블룸 필터(BF)는 조회(lookup) 성능과 공간 효율성을 높이기 위해 의도적으로 오류 허용(error tolerance)을 도입한 자료 구조입니다. 블룸 필터는 true 또는 fals

기본 개념카운팅 블룸 필터(Counting Bloom Filter)는 기존 블룸 필터(Bloom Filter)를 확장한 일반화된 자료구조로, 일련의 원소들이 주어졌을 때 특정 원소의 출현 횟수가 주어진 임계값(threshold)보다 작은지를 판별하기 위해 사용됩니다.블룸 필터의 일반화 형태이기 때문에 거짓 양성(false positive), 즉 실제로는 임계값 미만인데도 그 이상으로 판단할 가능성은 존재합니다. 반면 거짓 음성(false negative)은 절대 발생하지 않습니다. 다시 말해, 질의 결과는 항상 임계값 이상일 가능성

확률적 자료 구조에서 카운터를 설계할 때 가장 중요하게 고려해야 할 두 가지 요소는 바로 카운터의 크기와 오버플로 발생 가능성입니다. 이 글에서는 포아송 근사(Poisson approximation)를 기반으로 적절한 카운터 크기를 산정하는 방법과, 오버플로가 시스템에 미치는 영향을 살펴봅니다. 카운터 크기(Counter Size) 오버플로를 방지하기 위해서는 각 카운터가 저장할 수 있는 값의 범위가 충분히 커야 합니다. 카운터가 너무 작으면 값이 상한에 도달하는 순간 더 이상 정확한 정보를 담을 수 없게 되기 때문입니다.

블록 블룸 필터(Blocked Bloom Filter)는 캐시 효율성을 극대화하기 위해 고안된 확률적 자료 구조입니다. 표준 블룸 필터와 달리 전체 필터를 여러 개의 작은 블록으로 나누어 관리하며, 각 블록이 하나의 캐시 라인(cache-line)에 딱 맞도록 설계되어 캐시 미스를 크게 줄일 수 있다는 것이 핵심 아이디어입니다.블록 블룸 필터의 주요 특징먼저 하나의 메모리 블록을 선택합니다.그다음 해당 블록 내부의 로컬 블룸 필터를 선택합니다.메모리 블록 간에 불균형이 발생할 수 있습니다.연산은 효율적이지만, 표준 블룸 필터에 비해

트리 구조가 편향되면 탐색 성능이 급격히 저하됩니다. 이를 방지하기 위한 리밸런싱(Rebalancing) 알고리즘은 대표적으로 세 가지 방식으로 구현할 수 있습니다.1. Day-Stout-Warren(DSW) 알고리즘DSW 알고리즘은 실제 리밸런스 메서드를 구현하는 가장 고전적인 방법 중 하나입니다. 노드 수에 대해 선형 시간(O(n))으로 동작하며, 추가 메모리 없이 기존 트리를 완전히 균형 잡힌 형태로 재구성할 수 있다는 장점이 있습니다.다음은 기본적인 DSW 알고리즘의 절차를 의사 코드 형태로 정리한 것입니다.새로운 노드를 하