10000COW

플로이드 워셜 알고리즘이란? 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘이다. 2차원 테이블에 최단 거리 정보를 저장한다. 다익스트라 알고리즘과의 차이 - 소스코드가 다익스트라에 비해 짧아 구현이 간단하다. - 다익스트라의 경우 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 플로이드 워셜 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만, 매 단계마다 방문하지 않는 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다! 플로이드 워셜 알고리즘의 점화식 플로이드 워셜 알고리즘 직접 시도하기 [step 0] 그래프의 노드와 간선에 따라 최단 거리 테이블을 갱신한다. [step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블을 갱신한다. ..

벨만-포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘이다. 음의 가중치를 갖는 edge(간선)이 있을 때 사용하는 알고리즘이다. 다익스트라 알고리즘과 차이는 무엇인가? 다익스트라 알고리즘 - 매번 방문하지 않는 노드 중에서 최단거리가 가장 짧은 노드를 선택해 최단 거리를 구해나간다. - 음의 가중치를 갖는 edge(간선)이 없다면 최적의 해를 찾을 수 있다. - 시간 복잡도가 빠르다. 벨만-포드 알고리즘 - 매 단계마다 모든 edge(간선)을 전부 확인하면서 모든 노드간의 최단 거리를 구해나간다. - 음의 가중치를 갖는 edge가 있어도 최적의 해를 찾을 수 있다. - 시간 복잡도가 느리다. 즉, 모든 edge의 가중치가 양수일 때는 다익스트라 알고리즘을, 음의 가중치를 갖는..

들어가기 전에 다익스트라 알고리즘을 이해하기 위해 여러 유튜브와 블로그를 방문했었는데 대체로 설명이 어렵거나 생략이 많다.. 코드 설명도 자세하지 않아 아쉬움이 있었다. (특히, 블로그에 있는 표나 그림은 왜이렇게 딱딱한걸까.. 잘 모르는 사람에겐 거부감이 든다) 직접 하나하나 그려가보며 이해한 나의 깨달음을 다른 분들께 자세하고 쉽게, 마치 아무것도 모르는 어린 아이에게 설명하듯이 설명해보려고 한다. 그리고 시간이 지나면 잊어버리는 미래의 나를 위하여 상세히 기술해보았다. 자세한 예시부터 점점 과정을 추상화해나가므로 이해하기 쉬울 것이라고 생각한다. 다익스트라 알고리즘이란? 그래프의 한 정점(Vertex 또는 Node)에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘으로, 최단 경로 문제에 사용된다..

BFS는 큐를 이용한 반복 구조로 구현한다. 먼저 큐를 이용한 BFS Pseudo code를 보면서 어떻게 구현해야할지 생각해보자. 1) 큐를 이용한 BFS Pseudo code BFS(G, start_v) let Q be a queue label start_v as discovered Q.enqueue(start_v) while Q is not empty do v := Q.dequeue() if v is the goal then return v for all edges from v to w in G.adjacentEdges(v) do if w is not labeled as discovered then label w as discovered w.parent := v Q.enqueue(w) 2) 큐를 이..

1) 재귀를 이용한 DFS 구현 Pseudo code G는 그래프, v는 정점(vertex)일 때, DFS(G,v) lable v as discovered for all directed edges from v to w that are in G.adjacentEdges(v) do if vertex w is not labeled as discovered then recursively call DFS(G,w) 재귀를 이용한 DFS 구현 Python code def recursive_dfs(v, discovered=[]): discovered.append(v) for w in graph[v]: if w not in discovered: discovered = recusrive_dfs(w, discovered) ..