트리(tree)는 컴퓨터 과학에서 가장 널리 사용되는 계층적 자료구조 중 하나입니다. 그런데 트리는 크게 루트 트리(rooted tree, 뿌리 있는 트리)와 비루트 트리(unrooted tree, 뿌리 없는 트리)로 나눌 수 있으며, 이 두 구조는 근본적인 성격이 서로 다릅니다. 이번 글에서는 두 트리의 개념을 예시와 함께 살펴보고, 핵심적인 차이점을 명확하게 정리해 보겠습니다.루트 트리(Rooted Tree)의 예시루트 트리는 이름 그대로 ‘뿌리(root)’가 되는 특정 노드가 존재하는 트리입니다. 루트는 트리 전체의 시작점 역

단일 해시 함수의 한계해시 테이블에서 하나의 고정된 해시 함수를 사용할 때 근본적인 문제가 발생합니다. 테이블 크기 m이 전체 키 공간(universe)의 크기 u보다 훨씬 작다면(|U| ≫ m), 어떤 해시 함수 h를 선택하더라도 반드시 같은 해시 값으로 매핑되는 U의 거대한 부분집합이 존재하게 됩니다.즉, 입력 데이터가 어떤 특정 함수에 취약한 형태로 분포해 있다면 충돌(collision)이 집중적으로 발생하여 해시 테이블의 성능이 급격히 저하될 수 있습니다.해결 방법: 해시 함수 집합의 도입이 문제를 해결하기 위해서는 여러 개

체이닝(Chaining)을 활용한 해싱이란?해싱(Hashing)은 데이터를 빠르게 저장하고 검색하기 위한 대표적인 자료구조 기법입니다. 하지만 서로 다른 키가 동일한 해시 값에 매핑되는 충돌(Collision) 현상은 피할 수 없습니다. 체이닝(Chaining)은 이러한 충돌을 해결하는 대표적인 기법으로, 같은 해시 값에 해당하는 여러 요소를 하나의 연결 리스트(Linked List)로 묶어 저장하는 방식입니다.충돌 자체를 완전히 제거할 수는 없지만, 체이닝을 활용하면 충돌 발생 가능성을 줄이고, 동일한 해시 값을 가진 여러 요소도

열린 주소 지정(Open Addressing)이란?해시 테이블을 운용하다 보면 서로 다른 키가 동일한 해시 값을 가지는 충돌(Collision) 상황이 발생합니다. 열린 주소 지정은 이러한 충돌을 해결하는 대표적인 기법 중 하나입니다.체이닝(Chaining) 방식과 달리, 열린 주소 지정은 연결 리스트 같은 별도의 자료구조에 요소를 저장하지 않습니다. 대신 충돌이 발생하면 해시 테이블 내부의 다른 빈 슬롯을 찾아 데이터를 직접 삽입합니다. 따라서 효율적인 운영을 위해서는 해시 테이블의 크기가 저장할 키의 개수보다 커야 합니다.열린

해시 테이블에서 충돌(collision)을 해결하는 대표적인 방법 중 하나가 바로 개방 주소법(Open Addressing)입니다. 그중에서도 가장 기본이 되는 기법이 선형 조사(Linear Probing)입니다. 이 글에서는 선형 조사법의 동작 원리와 해시 함수의 구성, 그리고 실제 예제를 통해 삽입 과정까지 자세히 살펴보겠습니다.선형 조사란 무엇인가?개방 주소법에서는 충돌이 발생했을 때 다른 빈 슬롯을 찾아 데이터를 저장합니다. 일반적으로 사용되는 기본 해시 함수는 다음과 같습니다.h′(x) = x mod m여기서 m은 해시 테

이번 글에서는 개방 주소법(Open Addressing) 방식에서 해시 충돌을 해결하는 대표적인 기법인 2차 탐사(Quadratic Probing)에 대해 자세히 알아보겠습니다.2차 탐사의 기본 원리2차 탐사는 일반적인 해시 함수 h′(x) : U → {0, 1, ..., m – 1}을 기반으로 동작합니다. 개방 주소법에서 실제로 사용되는 해시 함수 h(x)는 이 일반 해시 함수에 2차식 형태의 항을 덧붙여 만든 하나의 이차 방정식입니다.먼저 일반 해시 함수는 다음과 같이 정의됩니다.h′(x) = x mod m그리고 실제 해시 함수

이 글에서는 개방 주소법(Open Addressing) 방식에서 충돌을 해결하는 대표적인 기법인 이중 해싱(Double Hashing)에 대해 자세히 살펴보겠습니다. 이중 해싱이란? 개방 주소법에서는 해시 테이블의 특정 슬롯이 이미 차 있을 경우, 다른 빈 슬롯을 찾아 데이터를 삽입해야 합니다. 이때 하나의 해시 함수만 사용하는 선형 탐사(Linear Probing)나 제곱 탐사(Quadratic Probing)와 달리, 이중 해싱은 두 개의 서로 다른 해시 함수를 조합하여 탐사 위치를 결정합니다. 먼저 일반적인 해시 함수 h

브렌트 방법(Brents Method) 개요이 글에서는 오픈 어드레싱(open addressing) 해싱과 관련된 브렌트 방법(Brents Method)에 대해 알아봅니다. 브렌트 방법은 일종의 휴리스틱(heuristic) 기법으로, 해시 테이블에서 성공적인 탐색(successful search)에 걸리는 평균 시간을 최소화하는 것을 목표로 합니다.이 방법은 원래 더블 해싱(double hashing) 기법에 적용하기 위해 고안되었지만, 선형 조사(linear probing)나 이차 조사(quadratic probing)처럼 다른

균형 이진 탐색 트리란 무엇인가?이번 글에서는 균형 이진 탐색 트리(Balanced Binary Search Tree)에 대해 알아보겠습니다. 이진 탐색 트리(Binary Search Tree, BST)는 각 노드의 왼쪽 자식에는 더 작은 값이, 오른쪽 자식에는 더 큰 값이 위치하는 이진 트리입니다.BST에서 원소를 탐색할 때의 평균 시간 복잡도는 O(log n)입니다. 이는 트리의 높이(height)에 의해 결정되는데, 문제는 BST의 속성을 유지하는 과정에서 트리가 한쪽으로 치우친 편향(skewed) 트리가 될 수 있다는 점입니

비대칭 해싱(Asymmetric Hashing)이란?비대칭 해싱은 다중 선택 해싱(multiple choice hashing)을 발전시킨 기법으로, 해시 테이블을 여러 개의 블록으로 나누고 각 블록 안에서 후보 위치를 선택함으로써 충돌을 효과적으로 줄이는 방식입니다. 이 글에서는 비대칭 해싱의 동작 원리와 대표적인 성능 분석 결과를 살펴보겠습니다.기본 개념비대칭 해싱에서는 해시 테이블을 d개의 블록으로 분할하며, 각 블록의 길이는 n/d입니다. 블록 i에 해당하는 탐색 값(probe value) xi(0 ≤ i ≤ d−1)은 다음

LCFS 해싱이란?이 글에서는 LCFS 해싱(Last Come First Serve Hashing)이 무엇인지 살펴보겠습니다. LCFS 해싱은 개방 주소법(open addressing) 전략 중 하나로, 기존의 충돌 해결(collision resolution) 방식을 변경한 기법입니다.FCFS 방식과의 차이점개방 주소법 기반 해싱 알고리즘을 분석해 보면, 두 요소가 충돌했을 때 우선순위가 높은 요소가 테이블에 먼저 삽입되고, 나중에 도착한 요소는 다른 위치를 찾아 이동해야 합니다. 즉, 개방 주소법의 해싱은 FCFS(First Co

그래프(Graph)는 대표적인 비선형 데이터 구조입니다. 이 자료구조에서는 값들을 노드(Node)에 저장하고, 노드들은 서로 다른 간선(Edge)으로 연결됩니다. 그래프 구조에 데이터를 저장할 수 있는 것처럼, 저장된 데이터를 실제로 활용하려면 그래프 내부에서 원하는 요소를 검색(탐색)하는 방법도 필요합니다.그래프에서 탐색을 수행하는 방법은 크게 두 가지가 있습니다. 바로 너비 우선 탐색(Breadth First Search, BFS)과 깊이 우선 탐색(Depth First Search, DFS)입니다.너비 우선 탐색(BFS, Br

방향 그래프에서의 깊이 우선 탐색(DFS)깊이 우선 탐색(Depth First Search, DFS)은 무방향 그래프와 방향 그래프 모두에 적용할 수 있는 기본적인 그래프 순회 알고리즘입니다. 특히 방향 그래프(Digraph)에서는 DFS를 수행하는 과정에서 간선들을 몇 가지 유형으로 분류할 수 있다는 점이 중요한 특징이며, 이는 사이클 검출이나 위상 정렬 같은 다양한 그래프 문제를 해결하는 핵심 단서가 됩니다.DFS 알고리즘은 탐색 과정에서 DFS 트리라고 불리는 트리 구조를 형성합니다. 방향 그래프에서 DFS를 수행하면 간선은

이 글에서는 데이터 구조에서 중요한 개념인 오일러 그래프(Eulerian Graph)와 해밀턴 그래프(Hamiltonian Graph)에 대해 살펴봅니다. 본격적으로 들어가기에 앞서, 이 두 개념을 이해하는 데 필수적인 기초 개념인 트레일(Trail)부터 먼저 알아보겠습니다.다음과 같은 그래프가 있다고 가정해 보겠습니다.그래프에서의 트레일(Trail)이란?트레일이란 간선(edge)들의 수열 (v1, v2), (v2, v3), …, (vk-1, vk)로 이루어진 경로를 의미합니다. 여기서 중요한 조건은 다음과 같습니다.정점(verte

이항 힙(Binomial Heap)은 여러 개의 이항 트리(Binomial Tree)로 구성된 자료구조입니다. 이항 힙은 우선순위 큐를 효율적으로 구현할 수 있어 알고리즘 설계에서 널리 활용됩니다. 이번 글에서는 이항 트리의 재귀적 정의부터 이항 힙의 성질과 예시까지 차근차근 살펴보겠습니다.이항 트리(Binomial Tree)란?이항 트리 Bk는 재귀적으로 정의되는 순서 트리(ordered tree)입니다.B0는 단 하나의 노드로 이루어진 가장 기본적인 형태입니다.Bk(k ≥ 1)는 두 개의 이항 트리 Bk-1을 서로 연결(link

피보나치 힙(Fibonacci Heap)은 여러 개의 트리(tree)를 모아놓은 자료구조로, 기본적으로 이항 힙(Binomial Heap)을 바탕으로 느슨하게 설계된 구조입니다. 두 자료구조는 비슷해 보이지만 중요한 차이점이 있습니다. 이항 힙을 구성하는 트리들이 순서가 있는(orderd) 트리라면, 피보나치 힙을 구성하는 트리들은 루트(root)를 가지고는 있지만 자식 간 순서가 정해져 있지 않은(unordered) 트리라는 점입니다.피보나치 힙의 노드 구조피보나치 힙에서 각 노드 x는 다음과 같은 포인터(pointer)들을 가지

개요이번 글에서는 이진 최대 힙(Binary Max Heap) 자료구조에 새로운 요소를 삽입하는 방법을 살펴보겠습니다. 최대 힙은 부모 노드의 값이 항상 자식 노드의 값보다 크거나 같은 성질(힙 속성)을 만족하는 완전 이진 트리입니다. 따라서 새 요소를 단순히 추가하는 것만으로는 부족하고, 삽입 후 힙 속성을 다시 복원하는 과정이 필요합니다.삽입 과정을 설명하기 위해 아래와 같은 초기 트리가 있다고 가정해 보겠습니다.삽입 알고리즘최대 힙에 요소를 삽입하는 절차는 다음과 같습니다.새 요소를 힙의 마지막 위치(배열의 끝)에 임시로 배치

이번 글에서는 이진 최대 힙(Binary Max Heap) 자료구조에서 요소를 삭제하는 방법을 살펴보겠습니다. 최대 힙은 부모 노드가 항상 자식 노드보다 크거나 같은 값을 가지는 완전 이진 트리로, 삭제 연산은 주로 루트(최댓값)를 제거할 때 사용됩니다.아래와 같은 초기 트리가 있다고 가정해 보겠습니다.삭제 알고리즘delete(heap, n) − Begin if heap is empty, then exit else item := heap[1] last := heap[n] n

정수 키를 위한 해시 테이블의 기본 구조해시 테이블(hash table)은 키(key)를 기반으로 데이터를 빠르게 저장하고 검색할 수 있는 대표적인 데이터 구조입니다. 이 글에서는 정수 키를 다루는 해시 테이블의 동작 원리와 완전 해시 함수(perfect hash function)의 개념을 살펴봅니다.키 값 𝑥는 전체 집합(universe) 𝑈 = {0, 1, …, 𝑢 – 2, 𝑢 – 1}에서 추출됩니다. 해시 함수 ℎ는 이 집합 𝑈를 정의역(domain)으로 가지며, 결과 값은 {0, 1, …, 𝑚 – 1} 범위 안에

나눗셈 해싱이란?이 글에서는 나눗셈을 활용한 해싱(division hashing) 기법에 대해 자세히 살펴보겠습니다. 이 방법에서는 다음과 같은 해시 함수를 사용합니다.ℎ(𝑥) = 𝑥 𝑚𝑜𝑑 𝑚즉, 입력값 x를 해시 테이블의 크기 m으로 나눈 나머지를 해시값으로 사용하는 방식입니다.해시 테이블의 구조이 해시 함수를 사용하려면 배열 A[0, …, m-1]을 유지 관리해야 합니다. 여기서 배열의 각 요소는 연결 리스트(linked list)의 머리(head) 노드를 가리키는 포인터 역할을 합니다. 배열 요소 A[i]가 가리키