깊이우선탐색

다익스트라(Dijkstra)? 다익스트라(Dijkstra) 알고리즘은 에츠허르 다익스트라가 고안한 알고리즘으로, 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 대표적인 최단 경로 알고리즘이다. 특징 그래프 방향의 유무는 상관 없으나, 간선들 중 하나라도 가중치가 음수이면 이 알고리즘은 사용할 수 없다. 음의 가중치를 가지는 간선이 있으며, 가중치 합이 음인 사이클이 존재하지 않는 경우 벨만-포드 알고리즘을 사용할 수 있다. 또한 그래프 내에 가중치 합이 음인 사이클이 존재한다면 무한히 음의 사이클을 도는 경우 경로 합이 음수 무한대로 발산하기 때문에 그래프 내의 최단 경로는 구성할 수 없다. 구현 P[A][B]는 A와 B사이의 거리라고 가정한다. 출발점으로부터 최단거리를..

백트래킹? 백트래킹은 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS는 큐의 크기가 매우 커질 수 있고 속도도 차이가 없기 때문에 경우의 수 구하기는 일반적으로 DFS가 편리하다. 출처: 나무위키 DFS & 백트래킹 백트래킹은 DFS를 사..