전체 글79 위상 정렬(Topological Sort) 완벽해부 (DAG와 진입 차수) 대학교 수강신청 기간을 떠올려 보십시오. '자료구조' 과목을 수강하려면 반드시 'C언어 기초'를 먼저 이수해야만 하고, '운영체제'를 들으려면 '컴퓨터 구조'를 먼저 들어야 합니다. 이처럼 우리의 현실 세계와 프로젝트 관리(PM)에서는 "어떤 작업을 수행하기 전에 반드시 선행되어야만 하는 작업의 순서"가 명확하게 존재하는 경우가 무수히 많습니다. 소프트웨어 빌드 시스템(Make, Gradle)에서 소스 코드의 의존성을 파악하여 빌드 순서를 결정하는 과정 역시 마찬가지입니다. 이렇게 복잡하게 얽힌 선후 관계의 규칙을 절대 위배하지 않고, 모든 작업을 차례대로 나열하여 올바른 실행 순서를 찾아주는 마법의 알고리즘이 바로 '위상 정렬(Topological Sort)'입니다. 그래프 이론 중에서도 실생활 응용력.. 2026. 2. 22. 유니온 파인드(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. 이전 1 ··· 5 6 7 8 9 10 11 ··· 14 다음
