Dijkstra(다익스트라) - 하나의 노드에서 다른 모든 노드까지의 최단경로를 구하는 알고리즘 - 간선들의 가중치를 기억해서 해당 노드까지의 경로가 최소로 갱신하는 알고리즘 import heapq ex_visit = [0 for _ in range(n+1)] #전의 값을 저장하는 곳 visit = [[''] for _ in range(n+1)] #전체 경로 나타내는 곳 def djikstra(start): global ex_visit, visit wei = [1000000] * (n+1) #최단거리 heap = [] heapq.heappush(heap,(0, start)) #(거리, node) wei[s] = 0 while heap: weight, node = heapq.heappop(heap) for..
### Floyd-Warshall(플로이드-워셜) ### : 그래프에서 모든 정점간 사이의 최단 거리 찾기 => 모든 최단경로 구하기 == 모든 정점 최단 경로 알 수 있다. + 모든 경로를 돌아보는 것으로 왔다갔다한 것을 다 알 수 있다. 시간 복잡도: O(n^3) for i in range(n): for j in range(n): for k in range(n): if dist[j][k] > dist[j][i] + dist[i][k] dist[j][k] = dist[j][i] +dist[i][k]
하노이의 탑
### 하노이의 탑 ### : 3개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있다. : n개의 원판 일 경우 원판을 모두 마지막 기둥으로 옮길 수 있는 방법의 수는 (2^n) - 1번 이다 (메르센 수) 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있으면 안된다. # 첫 번째 규칙 1->2, 1->3, 2->3을 잘 생각해서 재귀 하면 된다. # 재귀할 때 해당 code 다 끝나면 돌아온다. def hanoi(n, from_, to_, by_): if n == 1: print(from_, by_) else: hanoi(n-1, from_, by_, to_) print(from_, by_) hanoi(n-1, to_, from_, by_)