목록C++/알고리즘 (16)
나만의 작은 도서관
[알고리즘] 벨만-포드 알고리즘(Bellman-Ford Algorithm)
벨만-포드 알고리즘(Bellman-Ford Algorithm)이란?벨만-포드 알고리즘은 가중치가 있는 그래프(weighted graph)에서 시작점을 기준으로 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘과 동일하게 최단 거리를 찾아주는 알고리즘이지만, 벨만-포드 알고리즘은 다익스트라 알고리즘과는 다르게 음의 가중치가 있는 그래프에서도 사용가능하며, 음수 사이클 또한 찾아낼 수 있다는 점이 다르다. 하지만 모든 간선(E)을 확인하는 작업을 V-1번 반복하기 때문에 시간복잡도가 O(VE)로, O(ElogV)인 다익스트라 알고리즘보다 느리다는 단점이 있다. 알고리즘 분류는 매 순간 모든 간선을 완화하면서 최적해를 점진적으로 찾아가는 방식이기 때문에 다이나믹 프로그래밍(dyn..
[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘(Dijkstra Algorithm)이란?다익스트라 알고리즘은 가중치가 있는 그래프(weighted graph)중 음수 가중치가 없는 그래프에서 시작점을 기준으로 다른 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 최단 거리를 구하는 매 단계에서 가장 짧은 경로만 선택하기 때문에 그리디 알고리즘(greedy algorithm)으로 분류된다. 동작방식 1. 초기화 시작점에서 각 정점으로 가는 최단 거리를 저장할 배열을 생성한다. 배열은 시작점과의 거리를 0으로, 다른 정점들과의 거리는 무한대(INF)로 초기화한다. (편의상 시작점은 v1로 설정하였다.)아래 그림에서 Select, Add, Adjacent, Visited는 다음과 같은 의미를 가진다.Selec..
[알고리즘] 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이란?플로이드-워셜 알고리즘은 가중치가 있는 그래프(weighted graph)에서 모든 정점 쌍 사이의 최단 경로 길이를 구하는 알고리즘이다. 플로이드-워셜 알고리즘은 이전 단계에서의 최단 경로 길이를 저장해두었다가 현재 단계에서의 최단 경로 길이를 구할 때 재사용하기 때문에 다이나믹 프로그래밍(dynamic programming) 알고리즘으로 분류된다. 점화식플로이드-워셜 알고리즘은 다이나믹 프로그래밍 알고리즘으로 분류되기때문에 점화식이 존재한다. 정점 i를 vi, k번 이하의 정점들만 거쳐서 vi에서 vj로 가는 최단 경로 길이를 dist(k, i, j)라 했을 때(1 , 점화식은 다음과 같다. dist(k, i, j) = min(..
[알고리즘 부록] 트리를 순회하는 방법 3가지(프리오더, 인오더, 포스트오더)
트리의 순회 방법트리를 순회하는 방법은 크게 3가지가 있다. 각각의 방법은 다음과 같다.프리오더(preorder traversal) 또는 전위 순회: root -> 왼쪽 -> 오른쪽 순으로 순회하는 방식인오더(inorder traversal) 또는 중위 순회: 왼쪽 -> root -> 오른쪽 순으로 순회하는 방식포스트오더(postorder traversal) 또는 후위 순회 : 왼쪽 -> 오른쪽 -> root 순으로 순회하는 방식그림으로 보면 다음과 같다.동작방식 전위 순회는 처음 마주친 노드를 방문한다는 점이 특징이며, 중위 순회는 왼쪽부터 오른쪽으로 차례대로 방문한다는 점이, 후위 순회는 루트 노드를 가장 늦게 방문한다는 점이 특징이다.구현 코드struct node{ char left; c..
[알고리즘] 너비 우선 탐색(BFS)와 dx, dy 테크닉
너비 우선 탐색(BFS)이란?너비 우선 탐색(BFS, Breadth First Search)은 그래프 탐색을 진행할 때 깊이와 너비 중 너비를 우선적으로 탐색하는 방식을 의미하며, 깊이 우선 탐색(DFS, Depth First Search)와 동일하게 완전 탐색 알고리즘으로 분류된다. BFS를 이용한 그래프 탐색의 시간복잡도: O(V+E) or O(V^2)너비 우선 탐색은 깊이 우선 탐색과 동일하게 그래프에 존재하는 모든 정점들을 탐색하는 것이 주 목적이다. 따라서 너비 우선 탐색 또한 그래프가 어떻게 표현되었는가에 따라 시간복잡도가 다음과 같아진다. 그래프의 정점(Vertex)수를 V, 간선(Edge)수를 E라고 했을 때,그래프가 인접 리스트로 표현된 경우 O(V + E)그래프가 인접 행렬로 표현된 ..
[알고리즘] 백트래킹(backtracking)과 깊이 우선 탐색(DFS)
백트래킹이란? 백트래킹은 한국말로 "되추적"이라는 뜻으로, 이름에서 알 수 있듯 해답이 아닌 경우 이전 단계로 되돌아가 다른 경우를 선택하여 해답을 추적하는 방법이다. 백트래킹은 가능한 모든 경우를 탐색하기 때문에 완전 탐색(exhausted search) 알고리즘으로 분류되며, 일반적으로 상태공간트리(state space tree)나 그래프(graph)를 탐색할 때 사용한다. 상태공간트리란?상태공간트리는 탐색 알고리즘에서 문제의 해결 과정을 트리 구조로 표현한 것이다. 노드는 특정 과정에서의 상태를, 마디(경로)는 문제를 해결하기 위해 선택된 일련의 결정들을 의미한다. 틱택토에 대한 상태공간트리를 그림으로 표현하면 다음과 같다. 상태공간트리의 탐색 시간복잡도: O(M^N)백트래킹은 모든 경우의 수들을 ..