본문 바로가기

분류 전체보기54

유니온 파인드(Union-Find) 핵심정리 (Disjoint Set의 원리) 여러 대의 컴퓨터가 복잡한 랜선으로 얽혀 있는 거대한 네트워크 망을 관리한다고 상상해 보십시오. 무작위로 두 대의 컴퓨터를 골랐을 때, "이 두 컴퓨터가 서로 통신이 가능한 상태인가(같은 네트워크에 속해 있는가)?"를 실시간으로 빠르게 판별해야만 합니다. 만약 매번 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS)을 돌려서 경로를 찾는다면, 네트워크 규모가 커질수록 시스템은 심각한 과부하에 걸리게 될 것입니다. 이렇게 여러 개의 노드가 존재할 때, 어떤 노드들이 서로 같은 집합(Set)에 묶여 있는지를 가장 빠르고 효율적으로 관리하고 판별해 주는 마법의 자료구조가 있습니다. 바로 '유니온-파인드(Union-Find)', 학술적 용어로는 '서로소 집합(Disjoint Set)'입니다. 크루스칼(Krus.. 2026. 2. 22.
크루스칼(Kruskal) vs 프림(Prim) 알고리즘 (최소 신장 트리 비교) 국가에서 대한민국 100개의 주요 도시를 모두 연결하는 초고속 광랜 인터넷 케이블 공사를 진행한다고 상상해 보십시오. 각 도시를 잇는 케이블의 설치 비용은 모두 다릅니다. 국가의 예산은 한정되어 있으므로, 모든 도시가 통신망으로 끊김 없이 연결되면서도 전체 케이블 설치 비용의 합은 최소가 되도록 설계해야 합니다. 불필요하게 빙글빙글 도는 순환 도로(Cycle)를 만들어서 비용을 낭비해서도 안 됩니다. 이러한 현실 세계의 인프라 구축 문제를 컴퓨터 공학의 그래프 이론으로 완벽하게 해결해 주는 알고리즘이 바로 최소 신장 트리(Minimum Spanning Tree, 이하 MST)를 구하는 크루스칼(Kruskal)과 프림(Prim) 알고리즘입니다. 목적은 같지만 접근 방식이 정반대인 두 천재적인 알고리즘을 비.. 2026. 2. 22.
벨만-포드(Bellman-Ford) 이해 (음수 가중치 간선 처리법) 가장 빠르고 효율적인 최단 거리 탐색 기법으로 칭송받는 다익스트라(Dijkstra) 알고리즘에게는 절대 마주쳐서는 안 될 치명적인 약점이 하나 있습니다. 바로 '음수 가중치(Negative Weight)'를 가진 간선의 존재입니다. 도로망을 안내하는 내비게이션이라면 거리가 마이너스(-)가 될 리 없겠지만, 금융 시장의 환율 차익 거래(Arbitrage)를 분석하거나, 연료를 소모하는 대신 충전소가 있어 에너지를 환급받는 드론 경로를 계산할 때는 "비용이 줄어드는" 음수 가중치가 반드시 필요합니다. 다익스트라가 포기한 이 음수 가중치의 늪을 완벽하게 건너고, 나아가 시스템을 붕괴시키는 '음수 사이클'까지 감지해 내는 구원자, 벨만-포드(Bellman-Ford) 알고리즘의 동작 원리를 깊이 있게 해부해 봅니.. 2026. 2. 21.
다익스트라(Dijkstra) 알고리즘 완벽정리 (우선순위 큐 응용) 우리가 낯선 길을 갈 때 스마트폰에서 내비게이션 앱을 켜고 목적지를 입력하면, 단 1초도 지나지 않아 수백만 개의 도로 네트워크 속에서 '가장 빠르고 덜 막히는 최단 경로'를 화면에 그려줍니다. 도대체 컴퓨터는 그 복잡한 지도 데이터 속에서 어떻게 최단 거리를 순식간에 계산해 내는 것일까요? 이 경이로운 기술의 중심에는 1956년 천재 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 고안한 '다익스트라 알고리즘(Dijkstra Algorithm)'이 자리 잡고 있습니다. 하나의 시작점으로부터 다른 모든 정점까지의 최단 경로를 구하는 이 알고리즘은, 단순한 반복문에서 시작해 '우선순위 큐(Priority Queue)'를 만나며 완벽한 성능 최적화를 이루어냈습니다. 오늘 이 글에서는 .. 2026. 2. 21.
B-Tree와 B+Tree 완벽비교 (DB 인덱스 자료구조의 원리) 백엔드 개발자 면접에서 "데이터베이스 인덱스(Index)는 어떤 자료구조로 이루어져 있나요?"라는 질문에 단순히 "트리 구조입니다"라고 대답한다면 십중팔구 탈락의 고배를 마시게 됩니다. 관계형 데이터베이스(RDBMS)가 수억 건의 레코드 속에서도 0.01초 만에 원하는 데이터를 찾아내는 마법의 이면에는, 일반적인 이진 탐색 트리(BST)가 아닌 B-Tree와 그 진화형인 B+Tree라는 매우 정교하고 복잡한 자료구조가 숨어 있기 때문입니다. 오늘은 하드 디스크의 물리적 한계를 극복하고 DB 검색 속도를 극대화하기 위해 탄생한 이 두 가지 자료구조의 동작 원리와 결정적인 차이점을 완벽하게 해부해 보겠습니다.1. 일반 이진 탐색 트리(BST)를 DB에 쓰지 않는 이유B-Tree를 이해하기 위해서는 먼저 "왜.. 2026. 2. 21.
최소 공통 조상(LCA) 알고리즘 (트리 탐색 최적화 기법) 우리가 가족의 가계도(족보)를 펼쳐놓고 나와 내 육촌 형제가 도대체 어떤 조상님을 기준으로 피가 갈라졌는지 거슬러 올라가 본 적이 있으신가요? 이 과정을 컴퓨터 과학의 트리(Tree) 자료구조에 그대로 적용한 것이 바로 최소 공통 조상(Lowest Common Ancestor, 이하 LCA) 알고리즘입니다. 코딩 테스트의 그래프나 트리 심화 문제에서 두 노드 간의 최단 거리를 구하거나, 네트워크 라우팅 경로를 최적화할 때 반드시 등장하는 핵심 알고리즘입니다. 오늘은 가장 무식하게 부모를 찾는 O(N) 방식부터, 동적 계획법(DP)의 원리를 차용하여 O(log N)으로 탐색 속도를 비약적으로 끌어올리는 희소 배열(Sparse Table) 최적화 기법까지 완벽하게 정복해 보겠습니다.1. 최소 공통 조상(LC.. 2026. 2. 20.

티스토리툴바