TwentyTwentyOne

최소 공통 조상(LCA: Lowest Common Ancestor) 알고리즘 정복하기 – 개념, 세 가지 구현 방법, 실전 문제 응용 **LCA(Lowest Common Ancestor)**는 트리에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다.이는 트리 기반의 그래프 문제, 유전자 정보 분석, 네비게이션 경로, 파일 시스템 경로 찾기 등 실전에서 다양하게 활용됩니다.이번 글에서는 **LCA의 개념, 3가지 구현 방법(DFS + Parent 배열, Binary Lifting, 세그먼트 트리)**과 함께백준 실전 문제 적용법까지 완벽하게 정리합니다.✅ LCA란 무엇인가?트리에서 두 노드 A와 B의 조상 중에서 가장 깊은(가장 가까운) 공통 조상 노드를 말합니다.예를 들어, 다음과 같은 트리에서..

유니온 파인드(Union-Find) 알고리즘 완전 이해: 사이클 판별, 네트워크 그룹화, MST 응용까지**유니온 파인드(Disjoint Set, Union-Find)**는 그래프 이론에서 자주 쓰이는 대표적인 자료구조 중 하나로,서로소 집합을 관리하면서 **집합 간의 합치기(Union)**와 같은 집합인지 확인(Find) 작업을 빠르게 처리할 수 있게 해줍니다.이번 글에서는 유니온 파인드의 개념, 구현법, 경로 압축 최적화,그리고 **사이클 판별, 네트워크 연결 확인, 크루스칼 알고리즘(MST)**에의 응용까지 완전히 정리합니다.✅ 유니온 파인드란?여러 노드가 속한 **집합(components)**을 트리 구조로 표현하여두 노드가 같은 집합에 속해 있는지를 빠르게 확인하는 알고리즘🔹 핵심 연산연산명 ..

위상 정렬(Topological Sort) 완벽 이해: 개념, 구현, 사이클 판별까지 한 번에 정리**위상 정렬(Topological Sort)**은 방향 그래프(DAG: Directed Acyclic Graph)의 정점들을 선후 관계에 맞춰 순서대로 나열하는 알고리즘입니다.선수 과목 → 후수 과목, 작업 순서 지정, 빌드 순서 등 순차적 의존성을 가지는 문제에서 자주 활용됩니다.이번 글에서는 위상 정렬의 개념, 구현 방식(Kahn 알고리즘 / DFS 기반), 사이클 판별, 실전 예제까지 완벽하게 정리합니다.✅ 위상 정렬(Topological Sort)이란?방향성이 있는 그래프(DAG)에서,"A → B"라면 A를 B보다 먼저 나열하는 방식으로 모든 정점을 정렬🔹 위상 정렬의 전제 조건사이클이 없어야 한..

최소 신장 트리(MST) 완전 이해: 크루스칼(Kruskal) vs 프림(Prim) 알고리즘 비교와 구현**최소 신장 트리(Minimum Spanning Tree, MST)**는 그래프 알고리즘의 꽃이라 불립니다.특히 네트워크 비용 최소화, 전선 연결, 도로망 구성 등 비용 최소화 문제에서 많이 등장하며,**크루스칼(Kruskal)**과 프림(Prim) 알고리즘이 대표적인 해결책입니다.이번 글에서는 MST의 개념과 이 두 알고리즘의 차이, 작동 방식, Python 구현, 시간복잡도 비교까지 완전 정리합니다.🌲 MST(최소 신장 트리)란?그래프 내 모든 정점을 포함하면서사이클이 없고,간선의 가중치 합이 최소인 트리✅ 주요 특징그래프가 연결되어 있어야 함간선 수 = 정점 수 - 1MST는 여러 개가 존재할..

최단 경로 알고리즘 완전 정복: 다익스트라, 벨만포드, 플로이드 워셜 차이와 구현그래프에서 두 정점 사이의 **최단 경로(Shortest Path)**를 찾는 문제는 알고리즘에서 가장 중요한 주제 중 하나입니다.이 글에서는 세 가지 대표적인 최단 경로 알고리즘인다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), **플로이드 워셜(Floyd-Warshall)**을원리, 적용 조건, 구현 코드, 시간복잡도 중심으로 비교·정리합니다.🧭 언제 어떤 알고리즘을 써야 할까?알고리즘 음수 간선 모든 쌍 간선 시간복잡도 특징다익스트라❌ (음수X)❌ (단일 출발)O(E log V)양의 가중치만, 가장 빠름벨만-포드✅❌O(V × E)음수 가능, 음수 사이클 탐지플로이드-워셜✅✅O(V³)모든 노드 쌍 간 ..

그래프 이론 완벽 정리: 그래프의 개념부터 DFS, BFS 탐색 알고리즘까지그래프(Graph)는 현실 세계의 관계나 연결 구조를 표현하기 위한 자료구조입니다.소셜 네트워크, 지도 탐색, 웹 크롤링, 전력망 구성 등 다양한 문제를 **노드(Node)**와 **간선(Edge)**의 형태로 추상화할 수 있습니다.이번 글에서는 그래프의 개념, 표현 방식(인접 리스트/행렬), 그리고 탐색 알고리즘 DFS/BFS의 구현 및 활용법까지 체계적으로 정리합니다.✅ 그래프란 무엇인가?그래프는 정점(Vertex 또는 Node)과 간선(Edge)의 집합으로 이루어진 자료구조입니다.🔹 용어 정리용어 설명정점(Vertex)그래프에서의 노드간선(Edge)두 정점 간의 연결선방향 그래프간선에 방향이 있음 (u → v)무방향 그래프..

0/1 배낭 문제(Knapsack Problem)로 배우는 DP vs Greedy: 차이점과 실제 적용 비교**0/1 배낭 문제(0/1 Knapsack Problem)**는 동적 프로그래밍(DP)과 탐욕(Greedy) 알고리즘의 차이를 극명하게 보여주는 대표적인 문제입니다.이 문제를 통해 우리는 탐욕은 항상 최적해를 보장하지 않는다는 사실과, DP의 점화식 접근이 얼마나 강력한지를 체감하게 됩니다.이번 글에서는 0/1 Knapsack 문제를 중심으로, 두 방식의 접근법을 비교하고 구현까지 함께 진행합니다.🎒 0/1 Knapsack 문제란?문제 정의:무게 제한이 있는 배낭에 물건들을 넣는데, 각 물건은 **무게(W)와 가치(V)**를 가지고 있습니다.한 물건은 최대 1개만 선택할 수 있으며, 배낭에 넣을..

탐욕 알고리즘(Greedy Algorithm) 완벽 가이드: 개념, DP와의 차이, 실전 예제 분석탐욕 알고리즘(Greedy Algorithm)은 알고리즘 문제를 빠르고 직관적으로 해결할 수 있는 강력한 전략 중 하나입니다.하지만 항상 최적의 해를 보장하지는 않기 때문에, 언제 사용해야 할지 문제의 조건과 특성을 정확히 파악하는 것이 핵심입니다.이번 글에서는 탐욕 알고리즘의 원리, 동적 프로그래밍과의 차이점, Greedy 문제에서 자주 보이는 패턴 및 실전 예제를 차근차근 정리합니다.✅ 탐욕 알고리즘(Greedy)이란?탐욕 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 하는 알고리즘입니다.전체적인 최적해를 구하려는 것이 아니라, **매 순간의 지역 최적해(Local Optimal Solution)**..

동적 프로그래밍(Dynamic Programming) 완전 정복: 개념, 점화식, 실전 예제까지동적 프로그래밍(DP)은 알고리즘 중 가장 강력하지만 가장 어려워하는 주제 중 하나입니다.하지만 제대로 이해하면, 복잡한 문제를 빠르고 우아하게 해결할 수 있는 강력한 도구입니다.이번 글에서는 동적 프로그래밍의 정의, 핵심 원리, 점화식 세우는 법, 탑다운/바텀업 방식, 실전 예제까지 단계별로 확실하게 정리합니다.✅ 동적 프로그래밍(DP)이란?동적 프로그래밍은 복잡한 문제를 여러 개의 작은 문제로 나누고, 각 문제의 정답을 저장하여 중복 계산을 방지하는 알고리즘 기법입니다.🔹 언제 사용하는가?문제를 작은 하위 문제(subproblem)로 나눌 수 있을 때중복되는 하위 문제가 존재할 때최적 부분 구조(optim..

재귀(Recursion)와 분할정복(Divide & Conquer) 완벽 이해: 원리, 구현, 실전 예제까지재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법이며, 분할정복은 문제를 쪼개서 해결하는 알고리즘 설계 전략입니다.이 두 개념은 서로 매우 밀접하며, 실제로 합병 정렬, 이진 탐색, 퀵 정렬, 하노이 탑 등 다양한 문제에 활용됩니다.이번 글에서는 재귀 함수의 구조와 동작 원리, 그리고 분할정복 패턴의 실전 적용법을 함께 알아보겠습니다.✅ 재귀(Recursion)란?재귀 함수는 자기 자신을 호출하여 문제를 해결하는 함수입니다.대부분의 재귀 함수는 **종료 조건(Base Case)**이 반드시 존재해야 하며, 문제를 점점 더 단순한 형태로 줄여가야 합니다.📌 기본 구조def recursive(): ..