ITPE * JackerLab

개요SkipListMap은 Skip List 자료구조를 기반으로 구현된 정렬된 Key-Value Map입니다. 트리 기반 구조(B-tree, AVL, Red-Black Tree)와 달리 난수 기반의 링크드 리스트 계층 구조를 활용하여, **검색, 삽입, 삭제 작업을 평균 O(log n)**의 성능으로 수행할 수 있으며, Java의 ConcurrentSkipListMap, Redis, RocksDB 등에서 활용됩니다.1. 개념 및 정의SkipListMap은 기본적으로 Skip List라는 자료구조를 기반으로 구성된 맵(Map)으로, Key를 기준으로 정렬된 상태를 유지하며, 중복되지 않는 키와 연관된 값을 저장합니다. Skip List는 여러 층의 연결 리스트를 사용하여 빠른 탐색을 가능하게 하는 구조이며..

개요Lazy Propagation(지연 전파)은 Segment Tree(세그먼트 트리)에서 구간 단위 업데이트를 효율적으로 처리하기 위한 기술입니다. 일반적인 세그먼트 트리는 단일 요소 갱신에는 O(log n)의 성능을 제공하지만, 구간 전체를 갱신할 경우 모든 관련 노드를 업데이트해야 하므로 비효율적일 수 있습니다. 이때 실제 갱신을 지연하고 필요한 시점에만 적용함으로써 업데이트와 질의 연산 모두를 O(log n) 시간으로 유지할 수 있습니다.1. 개념 및 정의Lazy Propagation은 “지금 당장 처리하지 않아도 되는 업데이트는 나중에 처리하자”는 아이디어입니다. 즉, 구간 업데이트를 수행할 때:하위 노드로 즉시 갱신하지 않고,lazy[] 배열에 갱신 정보를 저장해두고,이후 질의나 하위 노드 접..

개요Segment Tree(세그먼트 트리)는 배열 또는 수열에서 **특정 구간에 대한 질의(Query)와 갱신(Update)**를 효율적으로 수행하기 위한 이진 트리 기반의 고급 자료구조입니다. 구간 합, 최소값/최대값, 최빈값, 최대공약수(GCD) 등 다양한 집계 연산을 O(log n) 시간 내에 처리할 수 있어, 알고리즘 문제, 게임 서버, 실시간 분석 시스템 등에서 널리 사용됩니다.1. 개념 및 정의Segment Tree는 크기 n의 배열에 대해 다음과 같은 연산을 빠르게 수행할 수 있는 트리입니다:build(): 배열을 기반으로 트리 구성 (O(n))query(l, r): 구간 [l, r]에 대한 집계 결과 반환 (O(log n))update(i, v): i번째 요소를 v로 갱신 (O(log n)..

개요Fibonacci Heap은 그래프 알고리즘에서 중요한 역할을 하는 우선순위 큐 구현 구조로, 특히 Decrease-Key, Merge 연산에서 탁월한 이론적 성능을 보이는 자료구조입니다. 이름은 노드 수가 피보나치 수열을 따르는 구조적 특성에서 유래하며, Dijkstra, Prim 알고리즘의 이론적 시간 복잡도를 낮추는 데 핵심 역할을 합니다.1. 개념 및 정의Fibonacci Heap은 연결 리스트 기반의 느슨한 구조로 구성된 **최소 힙(min heap)**이며, 여러 개의 트리를 루트 리스트로 구성하고 lazy 방식으로 병합 및 삽입을 처리합니다.창시자: Fredman과 Tarjan (1984)특징: 느슨한 균형 유지, 지연된 구조 조정(lazy consolidation)용도: 최단 경로 탐색..

개요Splay Tree는 자주 접근하는 노드를 루트로 끌어올려 접근 성능을 최적화하는 자가 조정형(Self-adjusting) 이진 탐색 트리입니다. 특별한 균형 기준 없이, 최근 접근 노드를 우선시하며 트리 구조를 동적으로 재조정하는 방식으로, 캐시 성능을 높이고 평균 연산 시간을 줄이는 데 효과적입니다.1. 개념 및 정의Splay Tree는 1985년 Sleator와 Tarjan에 의해 제안된 트리 자료구조로, 검색·삽입·삭제 연산 시 해당 노드를 루트로 끌어올리는(Splay) 과정을 통해 접근 성능을 개선합니다.목적: 자주 접근되는 노드를 빠르게 찾기 위한 트리 구조 최적화특징: 별도의 균형 조건 없이도 amortized O(log n) 성능 보장구조: 이진 탐색 트리의 변형 형태2. 연산 구조Sp..

개요Treap은 Tree와 Heap을 조합한 이름으로, 이진 탐색 트리(Binary Search Tree, BST)와 힙(Heap) 구조의 특성을 동시에 만족하는 확률적 자료구조입니다. 키에 대해 이진 탐색 트리 성질을, 우선순위에 대해 힙 성질을 유지함으로써 삽입, 삭제, 탐색 모두 평균적으로 O(log n) 시간 복잡도를 제공하며, 균형 잡힌 트리 구조를 확률적으로 유지할 수 있습니다.1. 개념 및 정의 항목 내용 정의각 노드가 키(Key)와 우선순위(Priority)를 가지며, 키는 BST, 우선순위는 힙 성질을 만족하는 이진 트리목적자가 균형(self-balancing) 유지로 빠른 탐색, 삽입, 삭제 지원필요성명시적 리밸런싱 없이 트리 높이 최적화를 달성하여 성능 향상Treap은 간단한 구조와..

개요Skip List는 연결 리스트(linked list)에 다층 구조를 추가하여 이진 탐색 트리와 유사한 빠른 탐색, 삽입, 삭제를 지원하는 자료구조입니다. 평균적으로 O(log n) 시간 복잡도를 제공하며, 균형 유지가 복잡한 트리 구조 대신 간단한 구조로 고성능을 실현할 수 있어 데이터베이스, 인메모리 캐시 시스템 등 다양한 분야에서 활용됩니다.1. 개념 및 정의항목내용정의다층 연결 리스트를 사용하여 탐색 성능을 향상시키는 확률적(probabilistic) 자료구조목적이진 탐색 트리 수준의 탐색 속도 확보 및 구현 단순화필요성정렬된 데이터에서 빠른 검색, 삽입, 삭제를 지원하고 트리 리밸런싱 복잡성 감소Skip List는 간결한 구조와 높은 효율성으로 현대 시스템 설계에 널리 사용되고 있습니다.2...

개요AVL 트리는 데이터 구조 중 하나로, 모든 노드가 스스로 균형을 유지하도록 설계된 자가 균형 이진 탐색 트리(Self-Balancing Binary Search Tree)입니다. 삽입, 삭제 시 트리의 높이 균형을 유지함으로써 탐색, 삽입, 삭제 연산에서 최악의 성능을 보장하며, 데이터베이스 인덱스, 캐시, 메모리 기반 검색 등 다양한 분야에서 활용됩니다. 본 포스트에서는 AVL 트리의 개념, 원리, 구현 방식 및 다른 트리와의 비교를 다룹니다.1. 개념 및 정의 항목 설명 정의각 노드의 왼쪽과 오른쪽 서브트리 높이 차이가 1 이하인 이진 탐색 트리명칭 유래1962년 G.M. Adelson-Velsky와 E.M. Landis가 제안한 이름의 약자핵심 특성트리의 균형 인수(Balance Factor..

개요큐(Queue)는 먼저 들어간 데이터가 먼저 나오는 선입선출(First-In, First-Out, FIFO) 구조를 가지는 선형 자료구조이다. 데이터는 **뒤(Rear)**에서 삽입되고, **앞(Front)**에서 삭제되며, 일상적인 줄서기, 프로세스 스케줄링, 버퍼 처리 등에 널리 사용된다. 파이썬에서는 collections.deque, 리스트, 큐 모듈 등을 통해 구현할 수 있다.1. 개념 및 정의 항목 설명 구조선형적, 한쪽에서는 삽입, 반대쪽에서는 삭제 수행주요 연산enqueue(삽입), dequeue(삭제), peek(앞 요소 확인), isEmpty원리FIFO (First-In, First-Out)2. 큐 연산 동작 예시초기: []enqueue(10) → [10]enqueue(20) → [..

개요스택(Stack)은 데이터가 일렬로 쌓이고, 가장 마지막에 삽입된 요소가 가장 먼저 제거되는 후입선출(Last-In, First-Out, LIFO) 원칙을 따르는 선형 자료구조이다. 삽입은 push, 삭제는 pop, 현재 요소 확인은 peek 또는 top 연산으로 수행되며, 재귀, 수식 계산, 괄호 검사, 웹 브라우저의 방문 기록 등 다양한 분야에서 널리 활용된다.1. 개념 및 정의 항목 설명 구조선형적, 한쪽 끝에서만 삽입 및 삭제 가능주요 연산push(삽입), pop(삭제), peek/top(최상단 확인), isEmpty대표 원리LIFO (Last-In, First-Out)2. 스택 연산 동작 예시초기: []push(10) → [10]push(20) → [10, 20]pop() → [10] (2..

개요연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터를 함께 저장하여 데이터를 선형으로 연결한 자료구조이다. 배열과 달리 메모리 상에서 연속적이지 않아도 되며, 삽입/삭제 연산이 유연하다는 장점이 있다. 리스트의 형태에 따라 단일(Singly), 이중(Doubly), 원형(Circular) 등으로 구분되며, 알고리즘과 시스템 구현에서 핵심적으로 활용된다.1. 개념 및 정의 구성 요소 설명 Node데이터(data) + 포인터(next)로 구성된 기본 단위Head연결 리스트의 시작 노드를 가리키는 포인터Tail마지막 노드를 의미하며, next는 None 또는 Head를 가리킴노드는 동적으로 생성되며, 메모리를 필요할 때마다 할당한다.2. 배열과의 차이점 비교항목배열(Ar..

개요순회 알고리즘(Traversal Algorithms)은 트리(Tree), 그래프(Graph)와 같은 비선형 자료구조 내의 모든 노드(또는 정점)를 체계적으로 방문하는 방법이다. 순회는 구조의 전체 상태를 파악하거나 특정 노드 검색, 경로 탐색, 연산 수행에 필수적이다. 이 글에서는 트리 순회와 그래프 순회를 중심으로 다양한 순회 알고리즘의 개념, 구현 방식, 시간 복잡도 및 활용 사례를 정리한다.1. 개념 및 정의순회(Traversal)는 자료구조에 저장된 데이터를 하나씩 방문하며 특정 작업(출력, 계산 등)을 수행하는 과정이다. 선형 구조는 단순 순차 탐색으로 충분하지만, 트리나 그래프는 분기 구조를 갖기 때문에 다양한 방식의 순회가 존재한다.2. 트리 순회(Tree Traversal) 순회 방식 ..

개요정렬 알고리즘은 데이터 집합을 일정한 기준(숫자 크기, 알파벳 순 등)에 따라 순서대로 정렬하는 알고리즘이다. 효율적인 정렬은 데이터 검색, 최적화, 통계 처리 등에서 성능 향상에 큰 영향을 미친다. 정렬 방식에 따라 내부 정렬, 외부 정렬, 안정 정렬, 불안정 정렬로 나뉘며, 시간/공간 복잡도에 따라 선택이 달라진다. 본 글에서는 대표적인 정렬 알고리즘들의 개념, 성능, 특징 및 활용 사례를 중심으로 정리한다.1. 정렬 알고리즘의 분류 분류 기준 유형 설명 구현 방식비교 기반 정렬요소 간 비교를 통해 순서 결정 (버블, 삽입, 병합 등)비비교 기반 정렬키 값을 직접 계산해 정렬 (계수, 기수 정렬)메모리 사용내부 정렬주 메모리 내에서 정렬 수행 (일반적인 정렬)외부 정렬디스크 등 외부 저장소에서..

개요탐색 알고리즘은 데이터 집합 내에서 특정 값을 찾기 위해 사용되는 알고리즘이다. 효율적인 탐색은 데이터 처리 성능에 직결되며, 자료구조와 문제 특성에 따라 다양한 탐색 방식이 활용된다. 선형 탐색처럼 단순한 방식부터 이진 탐색, 해시 탐색, 그래프 기반 탐색(DFS, BFS), 트리 탐색까지 광범위하게 존재한다. 본 글에서는 탐색 알고리즘의 개념, 종류, 시간 복잡도, 활용 사례를 중심으로 체계적으로 설명한다.1. 개념 및 정의탐색 알고리즘은 주어진 데이터 구조에서 특정 키나 값을 찾는 절차이다. 자료의 정렬 여부, 크기, 구조에 따라 탐색 방식의 효율이 달라지며, 경우에 따라 최적화된 알고리즘 선택이 중요하다.2. 탐색 알고리즘의 분류 분류 설명 적용 자료구조 선형 탐색데이터를 처음부터 끝까지 ..

개요선형 자료구조는 데이터를 순차적으로 저장하고 처리하는 구조로, 가장 기본적이고 널리 사용되는 데이터 조직 방식이다. 데이터의 삽입, 삭제, 탐색 등을 효율적으로 수행할 수 있도록 다양한 형태의 선형 구조가 존재하며, 메모리 구조와 응용 목적에 따라 적절한 자료구조를 선택하는 것이 중요하다. 본 글에서는 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue)의 개념, 구조, 특징, 활용 사례를 체계적으로 정리한다.1. 개념 및 정의 자료구조 정의 특징 배열동일한 타입의 데이터를 연속된 메모리 공간에 저장고정 크기, 인덱스 접근 빠름연결 리스트포인터를 통해 노드들이 연결된 구조동적 크기, 삽입/삭제 효율적스택한쪽 끝에서 삽입/삭제가 이뤄지는 LIFO 구조후입선출(..

개요자료구조(Data Structure)는 데이터를 효과적으로 저장하고 처리하기 위한 조직화된 방식이다. 알고리즘의 성능을 좌우하는 중요한 요소로, 효율적인 메모리 사용과 빠른 연산을 가능하게 해준다. 자료구조는 소프트웨어 개발, 시스템 설계, 데이터베이스, 인공지능, 보안 등 다양한 분야의 핵심 기반 기술로 활용된다. 본 글에서는 자료구조의 기본 개념, 분류, 주요 자료구조, 활용 사례를 체계적으로 정리한다.1. 개념 및 정의자료구조란 데이터를 저장하고, 검색하고, 삽입하고, 삭제하는 등의 연산을 효율적으로 수행할 수 있도록 데이터를 구조화하는 방식이다. 목적에 따라 선형, 비선형, 동적 구조 등으로 분류되며, 각 구조는 특정 문제 해결에 최적화되어 있다.2. 분류 분류 설명 예시 선형 구조데이터가..

개요스택(Stack)과 큐(Queue)는 **자료구조(Data Structure)**에서 가장 기본적인 개념으로, 데이터를 저장하고 관리하는 방식이 다릅니다. 스택은 LIFO(Last In, First Out) 구조를 가지며, 큐는 FIFO(First In, First Out) 방식을 따릅니다. 이러한 구조적인 차이로 인해 각각의 데이터 구조는 다양한 프로그래밍 및 알고리즘 문제에서 중요한 역할을 합니다. 본 글에서는 스택과 큐의 개념, 차이점, 주요 연산 및 활용 사례를 살펴봅니다. 1. 스택(Stack)이란?스택(Stack)은 후입선출(LIFO, Last In First Out) 방식으로 데이터를 저장하고 처리하는 자료구조입니다. 즉, 마지막에 들어온 데이터가 가장 먼저 제거되는 구조입니다.1.1..