ITPE * JackerLab

개요Suffix Tree(접미사 트리)는 문자열의 모든 접미사(suffix)를 트리 형태로 표현한 자료구조로, 문자열 검색, 부분 문자열 탐색, 반복 패턴 찾기 등 다양한 텍스트 알고리즘 문제를 O(m) 또는 **O(n)**의 시간 복잡도로 해결할 수 있도록 지원합니다. 특히 생물정보학, 텍스트 편집기, 데이터 압축 등 빠른 문자열 탐색이 필요한 분야에서 필수적인 자료구조입니다.1. 개념 및 정의Suffix Tree는 문자열 S의 모든 접미사를 루트에서부터 하위 노드로 이어지는 경로로 표현한 트라이(Trie) 기반의 압축 트리입니다. 다음과 같은 특징을 가집니다:각 경로는 S의 한 접미사를 나타냄리프 노드는 문자열의 각 접미사의 시작 인덱스를 저장내부 노드는 공통 접두사를 공유하는 부분 문자열을 표현※ ..

개요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)..

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

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

개요자료구조 알고리즘은 다양한 형태의 데이터를 저장하고 조작하기 위해 설계된 알고리즘으로, 효율적인 연산과 최적화된 문제 해결을 가능하게 한다. 이 알고리즘들은 배열, 스택, 큐, 트리, 그래프 등 특정 자료구조의 특성을 활용하여 구현되며, 소프트웨어 성능 향상에 직접적인 영향을 미친다. 본 글에서는 자료구조 알고리즘의 개념, 분류, 주요 알고리즘, 시간 복잡도 분석, 활용 사례를 중심으로 체계적으로 소개한다.1. 개념 및 정의자료구조 알고리즘은 특정 자료구조의 구조적 특성을 활용하여 데이터를 탐색, 삽입, 삭제, 정렬, 탐색 등의 연산을 수행하는 알고리즘이다. 문제 해결의 핵심 로직으로, 프로그래밍 전반에 걸쳐 필수적인 역할을 한다.2. 알고리즘 분류 분류 설명 주요 자료구조 탐색 알고리즘원하는 데..

개요자료구조(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..