STUDY

import heapq def dijkstra(u): # 시작 셋팅 D[u] = 0 q = [] heapq.heappush(q, (D[u],u)) # 정점 갯수 만큼 반복 for i in range(V): # 가중치 최솟값 찾기 min_v = 987654321 now, u = heapq.heappop(q) # 방문 처리 visit[u] = 1 # 인접한 정점 업데이터 for v in range(V): if adj[u][v] != 0 and visit[v] == 0 and D[v] > D[u] + adj[u][v]: D[v] = D[u] + adj[u][v] heapq.heappush(q, (D[v],v)) #######################################################..

def nCr(n, r, s, k): if k == r: print(*comb) else: for i in range(s, n-r+k+1): comb[k] = i nCr(n, r, i+1, k+1) N = 10 R = 3 comb = [0] * R nCr(N, R, 0, 0)

최단 경로 정의 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 - 다익스트라(dijkstra) 알고리즘 음의 가중치를 허용하지 않음 - 벨만-포드(Bellman-Ford) 알고리즘 음의 가중치 허용 모든 정점들에 대한 최단 경로 - 플로이드-워샬(Floyd-Warshall) 알고리즘 다익스트라(dijkstra) 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 시작정점에서 끝정점까지의 최단 경로에 정점 x가 존재. 이때, 최단 경로는 시작정점에서 끝정점까지의 최단 경로와 x에서 t까지의 최단경로 구성. 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사 def di..

MST(최소비용신장트리) 그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장트리 n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n - 1개의 간선으로 이루어진 트리 최소 신장 트리(Minimum Spanning Tree) 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 이러한 MST를 구하는 2가지 알고리즘 Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 1) 임의 정점을 하나 선택해서 시작 2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택 3) 모든 정점이 선택될 때 까지 1), 2) 과정..

def perm(n, k): if k == n: print(p) return else: for i in range(k, n): p[k], p[i] = p[i], p[k] perm(n, k+1) p[k], p[i] = p[i], p[k] p = [1, 2, 3] perm(3, 0) def f(n, m, k): if n == k: print(p) else: for i in range(m): if u[i] == 0: u[i] = 1 p[k] = arr[i] f(n, m, k+1) u[i] = 0 p = [0] * 3 arr = [1,2,3,4,5] u = [0] * len(arr) # mPn, 몇번째 수인지 f(3, 5, 0)