나만의 작은 도서관

A* 알고리즘(A star algorithm)이란?A* 알고리즘은 가중치가 있는 그래프(weighted graph)에서 시작점과 도착점이 주어졌을 때 최단 거리를 구하는 휴리스틱 기반의 알고리즘이다. 다익스트라 알고리즘에서 변형된 알고리즘이며, 동작 방식 또한 유사하지만 특정 지점까지의 추정 거리를 고려한다는 점에서 다르다. A* 알고리즘은 다익스트라 알고리즘보다 빠르게 두 정점 간의 최단 경로를 구해낸다는 점 때문에 게임 내에서 길 찾기 기능으로 사용되며, 대표적으로 스타크래프트가 A* 알고리즘을 사용하였다. (특정 게임에서는 A* 알고리즘마저도 느려 A* 알고리즘보다 빠른 JSP 알고리즘을 사용하기도 한다.) A* 알고리즘의 구성 요소g(n): 시작점에서 현재 정점까지의 실제 경로 비용.h(n): 현..

벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?벨만-포드 알고리즘은 가중치가 있는 그래프(weighted graph)에서 시작점을 기준으로 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과 동일하게 최단 거리를 찾아주는 알고리즘이지만, 벨만-포드 알고리즘은 다익스트라 알고리즘과는 다르게 음의 가중치가 있는 그래프에서도 사용가능하며, 음수 사이클 또한 찾아낼 수 있다는 점이 다르다. 하지만 모든 간선(E)을 확인하는 작업을 V-1번 반복하기 때문에 시간복잡도가 O(VE)로, O(ElogV)인 다익스트라 알고리즘보다 느리다는 단점이 있다.  알고리즘 분류는 매 순간 모든 간선을 완화하면서 최적해를 점진적으로 찾아가는 방식이기 때문에 다이나믹 프로그래밍(dyn..

다익스트라 알고리즘(Dijkstra Algorithm)이란?다익스트라 알고리즘은 가중치가 있는 그래프(weighted graph)중 음수 가중치가 없는 그래프에서 시작점을 기준으로 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최단 거리를 구하는 매 단계에서 가장 짧은 경로만 선택하기 때문에 그리디 알고리즘(greedy algorithm)으로 분류된다.  동작방식 1. 초기화 시작점에서 각 정점으로 가는 최단 거리를 저장할 배열을 생성한다. 배열은 시작점과의 거리를 0으로, 다른 정점들과의 거리는 무한대(INF)로 초기화한다. (편의상 시작점은 v1로 설정하였다.)아래 그림에서 Select, Add, Adjacent, Visited는 다음과 같은 의미를 가진다.Selec..

플로이드-워셜 알고리즘(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..

너비 우선 탐색(BFS)이란?너비 우선 탐색(BFS, Breadth First Search)은 그래프 탐색을 진행할 때 깊이와 너비 중 너비를 우선적으로 탐색하는 방식을 의미하며, 깊이 우선 탐색(DFS, Depth First Search)와 동일하게 완전 탐색 알고리즘으로 분류된다.  BFS를 이용한 그래프 탐색의 시간복잡도: O(V+E) or O(V^2)너비 우선 탐색은 깊이 우선 탐색과 동일하게 그래프에 존재하는 모든 정점들을 탐색하는 것이 주 목적이다. 따라서 너비 우선 탐색 또한 그래프가 어떻게 표현되었는가에 따라 시간복잡도가 다음과 같아진다. 그래프의 정점(Vertex)수를 V, 간선(Edge)수를 E라고 했을 때,그래프가 인접 리스트로 표현된 경우 O(V + E)그래프가 인접 행렬로 표현된 ..