[Algorithm] 다익스트라 알고리즘 : 최단 경로 탐색(1) - 배열

인트로 다익스트라 알고리즘은 그래프의 탐색 알고리즘으로 BFS가 가중치 없는 그래프의 최단경로를 찾는 알고리즘이라면 다익스트라 알고리즘은 가중치가 있는 그래프의 최단경로를 구할 때 사용된다. 참고로 다익스트라 길 찾기 알고리즘은 DFS, BFS와 마찬가지로 완전 탐색 알고리즘에 속한다. 다익스트라(Dijkstra) 이해하기 1) 아래와 같은 가중치 그래프가 있다. 0번 정점에서 시작해 5번 정점까지의 최단거리를 구해보자. 최단거리를 저장할 배열(DIST)이 다음과 같은 형태로 있다. DIST[ ∞, ∞, ∞, ∞, ∞, ∞ ] (+ 아직 최단거리를 모르니 모두 ∞로 초기화한다.) 2) 시작 정점인 "0"번 정점을 방문한다. 시작 정점인 "0"번 정점은 최단거리가 "0"이므로 DIST[ 0, ∞, ∞, ∞..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 31.
• textsms

[Algorithm] DFS (Depth First Search, 깊이 우선 탐색) 알고리즘

인트로 그래프의 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)를 구현해보려 한다. 그래프라는 건 추상적인 개념이다. 0번 정점과 1번 정점이 연결되어 있다는 정보만 있을 뿐 실질적으로 그래프를 구현하는 자료구조는 배열이 될 수도 리스트가 될 수도 벡터가 될 수 있다. 어떤 자료구조를 사용할진 개발자의 선택이다. 본 포스팅에선 C# 기반 배열과 리스트(List)로 구현하는 간단한 코드를 소개하려 한다. 결론부터 말하면 재귀 함수를 사용해 DFS를 구현했다. BFS가 궁금하다면? [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 인트로 ..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 17.
• textsms

[Data Structure] 트리(Tree)와 그래프(Graph) 이해하기

인트로 그래프 탐색 알고리즘인 BFS, DFS와 트리 탐색 알고리즘인 전위 중위 후위 순회를 정리하기 전에 배경지식인 트리와 그래프의 관계 그리고 특징을 정리하려 한다. 결론부터 말하면 트리는 특정 조건을 만족하는 그래프이다. 즉, 트리는 그래프이지만 그래프는 트리가 아니다. 그래프(Graph) 그래프는 현실에 존재하는 개체 간의 관계를 표현하는 하나의 표기법일 뿐이다. 현실에서도 그래프를 찾아볼 수 있으며 흔히 보는 지하철 노선도가 그래프이다. 기흥이라는 점이 개체, 기흥과 강남대를 이어주는 선이 관계이다. 컴퓨터공학적인 시선으로 그래프를 바라보면 개체는 노드(Node)로, 관계는 간선(Edge)으로 표현된다. 그래프도 여러 종류가 존재한다. 대표적으로 1) 무방향 그래프 (Undirected Grap..

• format_list_bulleted Data structure
• · 2021. 8. 16.
• textsms