나만의 작은 도서관

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이란?플로이드-워셜 알고리즘은 가중치가 있는 그래프(weighted graph)에서 모든 정점 쌍 사이의 최단 경로 길이를 구하는 알고리즘이다. 플로이드-워셜 알고리즘은 이전 단계에서의 최단 경로 길이를 저장해두었다가 현재 단계에서의 최단 경로 길이를 구할 때 재사용하기 때문에 다이나믹 프로그래밍(dynamic programming) 알고리즘으로 분류된다. 점화식플로이드-워셜 알고리즘은 다이나믹 프로그래밍 알고리즘으로 분류되기때문에 점화식이 존재한다. 정점 i를 vi, k번 이하의 정점들만 거쳐서 vi에서 vj로 가는 최단 경로 길이를 dist(k, i, j)라 했을 때(1 , 점화식은 다음과 같다. dist(k, i, j) = min(..

트리의 순회 방법트리를 순회하는 방법은 크게 3가지가 있다. 각각의 방법은 다음과 같다.프리오더(preorder traversal) 또는 전위 순회: root -> 왼쪽 -> 오른쪽 순으로 순회하는 방식인오더(inorder traversal) 또는 중위 순회: 왼쪽 -> root -> 오른쪽 순으로 순회하는 방식포스트오더(postorder traversal) 또는 후위 순회 : 왼쪽 -> 오른쪽 -> root 순으로 순회하는 방식그림으로 보면 다음과 같다.동작방식 전위 순회는 처음 마주친 노드를 방문한다는 점이 특징이며, 중위 순회는 왼쪽부터 오른쪽으로 차례대로 방문한다는 점이, 후위 순회는 루트 노드를 가장 늦게 방문한다는 점이 특징이다.구현 코드struct node{ char left; c..