jundyu 님의 블로그

들어가며이번 글은 최소 신장 트리를 구하는 알고리즘 중 하나인 Prim에 대해 설명하는 글입니다. 글을 읽기 전에 아래의 링크에서 그래프 이론 및 그래프 탐색 글을 읽어보는 것을 추천합니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Prim 알고리즘을 설명하기 전에 최소 신장 트리에 대해 간략하게 설명하면서 시작하겠습니다. 최소 신장 트리 (MST : Minimum Spanning Tree)1. 정의우선 트리(Tree)의 사전적 정의는 사이클이 없고, 모든 정점이 연결된 무방..

들어가며제목에서 알 수 있듯이 이번 글은 위상 정렬을 위한 Kahn's 알고리즘에 대한 글입니다. 그래프와 관련된 알고리즘이므로 아래의 그래프 이론과 해당 글에 연계된 그래프 탐색 알고리즘 글들을 먼저 읽어보면 이해하기 쉽습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com 위상 정렬 : Topological Sort1. 개념위상 정렬이란 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것입니다. 사전적 의미로는 어려울 수 있는데, 쉽게 말하면 해야할 일의 순서를..

들어가며이번 글은 벨만 포드 알고리즘에 관한 포스팅입니다. 만약 그래프 이론이나 다른 그래프 탐색 알고리즘들을 모른다면 먼저 읽어보고 오는 것을 추천합니다. 아래의 링크에 그래프 이론 및 탐색에 관한 내용이 잘 나와있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Bellman-Ford : 벨만 포드1. 알고리즘 명칭Bellman-Ford라는 알고리즘의 명칭은 "Richard Bellman"와 "Lester Ford Jr."이라는 수학자의 이름에서 유래되었습니다. 벨만 포..

들어가며이번 글은 그래프 탐색에 관한 글로 읽기 전에 아래의 링크에서 그래프 이론을 숙지하고, 너비 우선 탐색 및 데이크스트라 알고리즘을 먼저 익히고 나면 정말 쉽게 배울 수 있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com [Algorithm] BFS 알고리즘 with JAVA들어가며BFS 알고리즘을 공부하기에 앞서 그래프 이론을 먼저 공부하면 이 글을 이해하는 데 더 도움이 될 것 같습니다! 아래의 링크에 그래프 이론에 관한 개념이 잘 정리되어 있습니다. [Algorith..

들어가며벌써 3번째 그래프 탐색 알고리즘에 관한 글을 쓰게 되었습니다. 이번 글 역시 아래의 링크를 통해 그래프 이론을 먼저 숙지하고 읽는 겻을 추천드립니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Dijkstra : 데이크스트라1. 알고리즘 명칭Dijkstra라는 알고리즘의 명칭은 "Edsger Dijkstra"라는 네덜란드의 컴퓨터 과학자의 이름에서 유래되었습니다. 네덜란드식 발음으로는 데이크스트라가 맞지만 한국에선 흔히 다익스트라로도 많이 알려져있습니다. 따라서 이번 ..

들어가며BFS 알고리즘을 공부하기에 앞서 그래프 이론을 먼저 공부하면 이 글을 이해하는 데 더 도움이 될 것 같습니다! 아래의 링크에 그래프 이론에 관한 개념이 잘 정리되어 있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com 이번 글에선 그래프를 탐색하는 방식 중 너비 우선 탐색(BFS)에 대해 알아보겠습니다. BFS : Breadth First Search1. 그래프를 탐색하는 목적일반적으로 그래프의 탐색은 특정 목적지까지의 최단 경로를 구하거나 그래프의 전체적인 구조를 ..

들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한 알고리즘 문제를 해결할 수 있게 됩니다. 이번 포스트에선 그래프가 무엇인지, 그래프는 어떤 방식으로 표현되는지, 그래프는 어떤 유형이 있는지, 마지막으로 그래프를 탐색하는 알고리즘에 대해 다뤄보려고 합니다. 이론 위주로 다루기 때문에 특정 언어에 국한되지 않습니다. 그래프 이론: Graph Theory1. 그래프란 그래프는 정점과 간선으로 이루어진 자료구조입니다. 쉽게 말하면 점과 다른 두 점을 서로 연결하는 선으로 이루어진 도형입니다. 2. 그래프의 특징그래프는 비선형적 구조입니다. 따라서 현실 세계의 다양한..

들어가며플로이드 워셜(Floyd-Warshall) 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘입니다. 3중 for문을 사용해서 전체 경로에 대해 지나칠 수 있는 노드를 점차 확장하며 가장 적은 비용의 경로를 찾아냅니다. 1번 노드 혹은 마지막 노드부터 순차적으로 확장하는 다이나믹 프로그래밍의 일종입니다.플로이드 워셜 알고리즘은 구현은 쉽지만 처음 접한다면 어려울 수 있으므로 그래프, 인접 행렬, DP(Bottom Up의 Tabulatoin)의 개념을 미리 숙지하고 보면 더 좋습니다. Floyd-Warshall 알고리즘1. 개요플로이드 워셜 알고리즘은 1962년 로버트 플로이드가 현재 사용되는 형태로 발표한 알고리즘으로 플로이드 알고리즘, 로이-워셜 알고리즘 등의 이름으로도 불립니다.플로..