TwentyTwentyOne

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

최단 경로 알고리즘 완전 정복: 다익스트라, 벨만포드, 플로이드 워셜 차이와 구현그래프에서 두 정점 사이의 **최단 경로(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개만 선택할 수 있으며, 배낭에 넣을..

스택(Stack)과 큐(Queue)의 구조, 차이점, 실전 활용법 완전 정리자료구조를 공부하다 보면 **스택(Stack)**과 **큐(Queue)**는 꼭 등장하는 핵심 개념입니다. 단순히 "쌓고 빼는 구조", "줄 서기 구조"라고 배우지만, 이 구조들이 실제로 어디에 쓰이고 어떻게 구현되는지를 제대로 이해하는 것이 중요합니다.이번 글에서는 스택과 큐의 개념, 차이점, 실제 코드 구현, 그리고 실무 및 코딩테스트에서 자주 등장하는 활용 사례까지 낱낱이 파헤쳐 보겠습니다.✅ 스택(Stack)이란?스택은 LIFO(Last In, First Out) 구조, 즉 나중에 넣은 데이터가 먼저 나오는 구조입니다.🔹 특징데이터의 삽입(push)과 삭제(pop)이 한쪽(top)에서만 이루어짐재귀 호출, 웹 브라우저 히..

배열 vs 연결리스트 완전 비교: 자료구조 선택 기준과 실제 예제 코드자료구조를 공부하다 보면 가장 먼저 마주치는 두 구조가 바로 배열(Array) 과 **연결리스트(Linked List)**입니다. 이 두 자료구조는 겉보기에는 유사해 보이지만, 메모리 사용 방식, 삽입/삭제 성능, 접근 방식 등에서 큰 차이를 보입니다.이번 글에서는 배열과 연결리스트의 핵심 차이점부터 장단점, 그리고 실제 코드를 통한 시간복잡도 분석까지 정리해보겠습니다.✅ 배열(Array)란?배열은 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조입니다.각 요소는 인덱스를 통해 O(1) 시간에 바로 접근할 수 있습니다.🔹 특징빠른 접근 속도 (O(1))삽입/삭제가 느림 (중간 삽입/삭제 시 O(n))메모리가 연속적으로 필요..