Algorithm/알고리즘(2)
-
[Graph] DFS와 BFS
DFS? Depth First Search의 약자이다. 즉, 깊이우선 탐색 알고리즘이다. 그렇다면 DFS 알고리즘은 어떻게 동작하는 지 알아보자. IDEA 위와 같이 생긴 그래프를 노드 0에서부터 깊이 탐색을 해보자. 1. 0 2. 0 -> 1 3. 0 -> 1 -> 5 5번 노드에서 갈 수 있는 노드가 없으므로 다시 뒤로 복귀한다. 4. 0 -> 1 -> 5 1번 노드 또한 더 이상 탐색할 수 있는 노드가 없으므로 0번으로 복귀한다. 5. 0 -> 1 -> 5 -> 2 0번에서 2번을 탐색할 수 있으므로 2번을 탐색한다. 6. 0 -> 1 -> 5 -> 2 -> 3 6. 0 -> 1 -> 5 -> 2 -> 3 -> 6 7. 0 -> 1 -> 5 -> 2 -> 3 -> 6 -> 7 7번 노드에서 0번으로..
2019.09.19 -
[Graph] 다익스트라
다익스트라 알고리즘? 그래프에서 노드들간의 최단 거리를 알아내기위해 사용하는 알고리즘이다. 다익스트라 알고리즘은 매우 직관적인 알고리즘이다. 그렇다면 다익스트라 알고리즘이 어떻게 동작하는지 알아보자. IDEA 예를 들어 아래와 같은 상황을 생각해보자. 위 와같은 지도를 보자. 집에서 각각의 상점까지의 최단거리를 알아내고자한다. 이때 다익스트라 알고리즘을 사용하여 해결해보자. 1. 처음 집에서 출발을 한다. 집에서 처음 출발할때, 가지고 있는 정보는 집에서 집으로 갈 때, 0이라는 시간이 소요된다는 것 뿐이다. 이제 집에서 바로 갈 수 있는 장소들에 대해 탐색해보자. 2. 집에서 바로 갈 수 있는 장소들 중 상점, 영화관, 은행의 경우 기존의 거리(INF)보다 집에서 집까지의 거리 + 집에서 각 위치들 까..
2019.09.18