[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] 이진 탐색 트리 (Binary Search Tree, BST) + 전위 중위 후위 순회

인트로 그래프의 탐색 방법으로 DFS와 BFS가 대표적이다. 트리는 특정 조건을 만족하는 그래프이다. 따라서 트리에 BFS와 DFS 탐색 알고리즘을 적용할 수 있다. 본 포스팅에선 DFS에 기반한 이진 트리 탐색 알고리즘인 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)를 다루려 한다. (+ 2021.09.01 추가 이진 트리의 순회 알고리즘을 소개하며 이진 트리와 이진 탐색 트리를 모두 소개하다 보니 전달하려는 의미가 모호해졌네요.일반적으로 이진 트리의 순회는 전위 중위 후위 순회가 있습니다. 물론 이진 탐색 트리도 일종의 이진 트리이기에 순회 가능합니다. 나아가 이진 탐색 트리는 "이진 탐색"에 기반한 추상..

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

[Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘

인트로 그래프의 탐색 알고리즘인 BFS(Breadth First Search, 너비 우선 탐색)를 구현해보려 한다. DFS와 다르게 BFS는 주로 한 가지 목적으로 사용된다. 그것은 가중치가 없는 그래프의 최단 경로를 구할 때 사용된다. 본 포스팅에선 C# 기반 배열과 리스트(List)로 BFS를 구현하는 간단한 코드와 최단 경로 출력 코드를 소개하려 한다. 결론부터 말하면 Queue를 사용해서 BFS를 구현했다. DFS가 궁금하다면? DFS (Depth First Search, 깊이 우선 탐색) 알고리즘 [Algorithm] DFS (Depth First Search, 깊이 우선 탐색) 알고리즘 인트로 그래프의 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)를 구현해보려 한..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 23.
• 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