알고리즘/그래프 순회(GraphTraversal) (5) 썸네일형 리스트형 [알고리즘] 최단 경로 탐색(데이크스트라 알고리즘) - 코딩밥상 데이크스트라(Dijkstra) 알고리즘이란? 최단 경로 탐색이란 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최솟값인 경로를 찾는 알고리즘입니다. 그 중 대표적인 알고리즘으로 데이크스트라 알고리즘이 있습니다. 이는 프림 알고리즘과 동작 방식이 상당히 비슷합니다. 다만 프림 알고리즘이 단순히 간선의 길이를 이용하여 어떤 간선을 먼저 연결할지 결정하는 데 비해 데이크스트라 알고리즘은 경로의 길이를 감안해서 간선을 연결한다는 점이 다릅니다. 또 다른 중요한 차이점은 데이크스트라 알고리즘의 경우 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다는 것입니다. 간단하게 데이크스트라 알고리즘에대해 정리하자면, 각 정점에는 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 각 정.. [알고리즘] 최소 신장 트리 알고리즘(Minimum Spanning Tree Algorithm) - 코딩밥상 최소 신장 트리(Minimum Spanning Tree)란? 각 간선 마다 가중치(Weight)를 갖는다면 표현할 수 있는 요소가 훨씬 다양해집니다. 신장 트리(Spanning Tree)의 'Spanning'의 뜻은 '떨어져 있는 둘 사이를 다리 등으로 연결한다'라는 뜻입니다. 즉, 신장 트리는 그래프의 모든 정점을 연결하는 트리입니다. 최소 신장 트리(Minimum Spanning Tree)란 여러 간선 중 가중치의 합이 최소가 되는 간선만 남긴 신장 트리입니다. 따라서 최소 가중치 신장 트리(Minimum Weight Spanning Tree)라고도 부릅니다. 이러한 특징을 가지는 최소 신장 트리를 만드는 알고리즘에는 대표적으로 프림(Prim)과 크루스칼(Kruskal)알고리즘이 있습니다. 먼저 프림.. [알고리즘] 위상 정렬(Topological Sort) - 코딩밥상 위상 정렬(Topological Sort)이란? '위상'이란 '어떤 정점이 다른 정점과의 관계 속에서 가지는 위치'라는 의미입니다. 이는 그래프 내 서로 인접한 정점 사이의 관계에 '위치'라는 속성이 존재한다는 뜻입니다. 이 위치는 간선 방향에 의해 결정됩니다. 간선을 뻗어내는 정점이 앞이 되고, 간선을 받는 정점이 뒤가 됩니다. 이 앞/뒤 또는 위/아래 관계를 차근차근 정렬하는 작업이 바로 위상 정렬입니다. 그런데 모든 그래프에 대해 위상 정렬을 할 수 있는 것은 아닙니다. 위상 정렬을 하기 위해선 몇가지 조건이 있습니다. 첫째로 그래프에 방향성이 있어야 하고, 둘째로 그래프 내에 사이클이 없어야 합니다. 이러한 조건을 만족하는 그래프를 DAG(Directed Acyclic Graph)라고 합니다. 정.. [알고리즘] BFS(넓이 우선 탐색) - 코딩밥상 넓이 우선 탐색(Breadth First Search)이란? '꼼꼼히 좌우를 살피며 다니자'는 원칙으로 그래프를 순회하는 알고리즘입니다. 넓이 우선 탐색에서는 시작 정점을 지난 후 깊이가 1인 모든 정점을 방문하고 그 다음에는 깊이가 2인 모든 정점을 방문합니다. 이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점을 방문하다가 더 이상 방문할 정점이 없을 때 탐색을 종료합니다. 대표적인 이용 방법은 그래프의 최단경로에 사용됩니다. 알고리즘의 동작 방식을 구체적으로 정리하자면, 시작 정점을 '방문했음'으로 표시하고 큐에 삽입합니다. 큐로부터 정점을 제거합니다. 제거한 정점의 인접 정점 중에서 아직 방문하지 않은 곳을 '방문했음'으로 표시하고 큐에 삽입합니다. 최종적으로 큐가 비면 탐색이 끝.. [알고리즘] DFS(깊이 우선 탐색) - 코딩 밥상 깊이 우선 탐색(Depth First Search)이란? '더 나아갈 길이 보이지 않을 때까지 깊이 들어간다'는 원칙으로 그래프 내의 정점을 방문하는 알고리즘입니다. 이 알고리즘은 길이 나오지 않을 때까지 그래프의 정점을 타고 깊이 들어가다가 더 이상 방문해왔던 정점 말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식으로 동작합니다. 대표적인 이용 방법은 그래프 정렬이나 미로 찾기 문제에서 사용됩니다. 알고리즘의 동작 방식을 구체적으로 설명하자면, 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시합니다. 이 정점과 이웃 정점(인접 정점) 중에 아직 방문하지 않은 곳을 선택하여 이를 시작 정점으로 삼고 다시 깊이 우선 탐색을 사직합니다.. 이전 1 다음
