CS/알고리즘

MST

MST 스패닝 트리 : 그래프의 모든 정점을 포함하는 트리 최소 스패닝 트리 : 가중치의 합이 가장 작은 스패닝 트리 Kruscal 1. 간선을 가중치 순으로 저장한다. 2. 간선을 순서대로 확인하면서 계속 추가한다. 사이클을 만드는 간선은 추가하지 않는다. 1. 간선을 가중치 순으로 저장한다. 2. 간선을 순서대로 확인하면서 계속 추가한다. - 두 정점이 같은 집합 안에 있다면 사이클을 만드는 간선이므로 무시한다 - 두 정점이 다른 집합 안에 있다면 union 연산을 수행하고 mst, mst_weight를 갱신한다. def kruscal(adj): # adj : (weight, from, to) 의 배열 mst = [] mst_weight = 0 adj.sort() uf = UnionFind(n) fo..

가중치 있는 최단 경로 문제

Dijkstra def dijkstra(sx): dist = [INF]*n; dist[sx] = 0 # (cost, x) 저장하는 min-heap hq = []; heapq.heappush(hq, (0, sx)) while hq: cost, x = heapq.heappop(hq) if cost > dist[x]: continue for nx, weight in adj[x]: newCost = cost + weight if newCost < dist[nx]: dist[nx] = newCost heapq.heappush(hq, (newCost, nx)) return dist 0 이상의 가중치를 갖는 그래프에 대해 한 정점으로부터의 최단거리 계산 요약 BFS와 비슷하지만 3가지가 다르다 ① (cost, nod..

BBST / union-find

BBST motivation : BST가 균형이 안맞으면 점차 연결리스트나 다름 없어짐 example AVL tree, Red-black Tree union-find disjoint set을 효율적으로 구현하는 자료구조 최적화 motivation : 균형이 안맞으면 점차 연결리스트나 다름 없어짐 모든 현실적인 입력에 대해 상수 시간에 작동 class UnionFind(): def __init__(self, maxSize = 100): self.parent = [i for i in range(maxSize)] self.rank = [0]*maxSize # 루트 노드를 반환 def find(self, a): if a == self.parent[a]: return a self.parent[a] = self.f..

DFS/BFS

DFS 그래프의 구조에 대해 알고 싶을 때 사용 dfs, dfsAll 을 이용한 전체 탐색을 주로 한다 example - component count - 간선의 종류 ( 트리 간선 / 순방향 간선 / 역방향 간선 / 교차 간선 ) - cycle detection ( 역방향 간선 발견 ) BFS 가중치 없는 그래프에서 최단 거리 문제를 해결할 때 사용 bfsAll 개념은 잘 사용하지 않는다 shortest path parent 배열을 만들고 각 정점이 부모 정점의 번호를 저장하도록 하면 된다. 루트 정점은 자기 자신의 번호를 저장한다. def shortestPath(x): path = [] while x != parent[x]: path.append(x) x = parent[x] path.append(x)..