분류 전체보기37 B-Tree & B+Tree 차이점 (DB 인덱스 원리) 관계형 데이터베이스(RDBMS)에서 수백만 건의 데이터 중 원하는 정보를 1초 미만의 짧은 시간에 찾아낼 수 있는 비결은 바로 인덱스(Index)에 있습니다. 그리고 이 인덱스를 구현하는 가장 핵심적인 알고리즘이 바로 B-Tree와 그 확장형인 B+Tree입니다. 대용량 데이터를 처리할 때 이진 탐색 트리(BST)는 트리의 높이가 너무 높아져 디스크 I/O 비용이 폭증하는 문제가 있지만, B-Tree 계열은 노드 하나에 여러 데이터를 담음으로써 트리의 높이를 획기적으로 낮춥니다. 이 글에서는 현대 데이터베이스 시스템이 왜 단순한 B-Tree가 아닌 B+Tree를 기본 인덱스 구조로 채택하는지, 그 기술적 차이점과 성능상의 이점을 심층 분석합니다.1. B-Tree: 균형 잡힌 다진 검색 트리B-Tree는 .. 2026. 2. 5. 트라이(Trie) 자료구조 완벽해부 (문자열 검색, 자동완성) 우리가 구글이나 네이버 검색창에 '자'를 입력했을 때 '자료구조', '자바스크립트'와 같은 추천 검색어가 순식간에 나타나는 원리를 궁금해한 적이 있으신가요? 수백만 개의 단어 중에서 사용자가 입력한 패턴을 실시간으로 찾아내는 이 마법 같은 기술의 배후에는 트라이(Trie)라는 자료구조가 존재합니다. 'Retrieval(검색)'에서 이름을 따온 트라이는 문자열을 저장하고 효율적으로 탐색하는 데 특화된 접두사 트리(Prefix Tree)입니다. 이 글에서는 트라이가 왜 검색 엔진과 자동완성 시스템의 표준이 되었는지, 해시(Hash)나 이진 탐색 트리(BST)와 비교하여 어떤 기술적 우위를 가지는지 심층 분석합니다.1. 트라이(Trie)의 구조와 핵심 개념트라이는 문자열의 각 문자를 노드(Node)로 저장하여.. 2026. 2. 4. 레드-블랙 트리(Red-Black Tree) 개념 (규칙, 사용처) 이진 탐색 트리(BST)의 편향 문제를 해결하기 위해 고안된 자료구조 중, 실무에서 가장 널리 쓰이는 것이 바로 레드-블랙 트리(Red-Black Tree)입니다. 앞서 다룬 AVL 트리가 '엄격한 균형'을 유지하여 검색 속도를 극대화했다면, 레드-블랙 트리는 '적당한 균형'을 유지하여 데이터의 삽입과 삭제 속도까지 최적화한 모델입니다. 이러한 특성 덕분에 C++의 STL(map, set), Java의 HashMap, 그리고 리눅스 커널의 스케줄러 등 고성능이 요구되는 시스템의 핵심 엔진으로 자리 잡았습니다. 이 글에서는 레드-블랙 트리가 어떻게 색상(Color)만으로 트리의 균형을 유지하는지, 그 5가지 절대 규칙과 활용 분야를 심층 분석합니다.1. 레드-블랙 트리(Red-Black Tree)의 핵심 .. 2026. 2. 4. AVL 트리 균형 원리 (회전, 높이 조절) 이진 탐색 트리(BST, Binary Search Tree)는 효율적인 데이터 검색을 위해 고안된 훌륭한 자료구조입니다. 하지만 데이터가 정렬된 상태로 순차적으로 입력될 경우, 트리가 한쪽으로 치우치는 편향(Skewed) 현상이 발생하여 최악의 경우 연결 리스트와 동일한 $O(N)$의 시간 복잡도를 가지게 됩니다. 이러한 치명적인 약점을 보완하기 위해 등장한 것이 바로 AVL 트리(Adelson-Velsky and Landis Tree)입니다. AVL 트리는 스스로 균형을 잡는(Self-Balancing) 최초의 알고리즘으로, 삽입과 삭제가 일어날 때마다 트리의 높이 균형을 맞추어 항상 $O(\log N)$의 성능을 보장합니다. 본 글에서는 AVL 트리가 어떻게 균형 인수(Balance Factor)를 .. 2026. 2. 4. 스택 2개로 큐 구현하기 (자료구조 응용) 소프트웨어 엔지니어링 면접이나 알고리즘 코딩 테스트에서 가장 빈번하게 등장하는 고전적인 문제 중 하나는 "스택(Stack) 두 개를 사용하여 큐(Queue)를 구현하시오"입니다. 얼핏 보면 단순한 자료구조 변환 문제처럼 보이지만, 이 질문의 이면에는 데이터의 흐름 제어와 시간 복잡도의 분할 상환 분석(Amortized Analysis)에 대한 깊은 이해가 깔려 있습니다. 후입선출(LIFO)의 성질을 가진 스택을 조합하여 어떻게 선입선출(FIFO)의 큐를 만들어낼 수 있을까요? 이 글에서는 그 논리적 배경과 구현 방법, 그리고 성능 분석까지 상세히 다룹니다.1. 문제의 핵심: LIFO를 FIFO로 역전시키기이 문제의 핵심은 자료구조의 입출력 순서를 뒤집는 것입니다. 스택(Stack): 나중에 들어온 .. 2026. 2. 3. 구간 합(Prefix Sum) 완벽정리 (1차원, 2차원 배열) 알고리즘 문제 해결, 특히 코딩 테스트나 대규모 데이터 분석에서 '구간 합(Range Sum)'을 구하는 문제는 매우 빈번하게 출제됩니다. $N$개의 데이터가 있을 때, 특정 구간의 합을 매번 반복문으로 계산하면 $O(N)$의 시간이 소요됩니다. 만약 이러한 질의(Query)가 $M$번 반복된다면 전체 시간 복잡도는 $O(N \times M)$이 되어, 데이터가 조금만 커져도 '시간 초과(Time Limit Exceeded)'를 피할 수 없습니다. 이때 필요한 기법이 바로 누적 합(Prefix Sum)입니다. 데이터를 미리 가공해 놓음으로써, 아무리 넓은 구간이라도 단 한 번의 연산($O(1)$)으로 합계를 구해내는 이 강력한 알고리즘의 1차원 및 2차원 배열 적용법을 완벽하게 정리해 드립니다.1. 1차.. 2026. 2. 3. 이전 1 2 3 4 5 6 7 다음
