본문 바로가기

CS3

[알고리즘] 다익스트라(Dijkstra) 다익스트라(Dijkstra) Dynamic Programming을 활용한 최단 경로 탐색 알고리즘 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용 작은 문제가 큰 문제의 부분 집합에 속해 있기에 DP라 볼 수 있다. 음의 간선은 포함할 Ex) 인공위성 GPS 소프트웨어 등에서 활용 자료구조 우선 순위 큐 이용 시작 노드를 넣는다. 타겟 노드를 빼고 그 노드와 연결된 다른 노드와 간선 가중치를 조회한다. 최소거리가 보장되는 경우에만 그 다음 노드를 우선 순위 큐에 넣는다. 주의할 점 0의 간선를 주의해야 한다. 0의 간선이 무한히 많은 경우, 범위를 제대로 지정해주지 않으면, 무한 루프를 돌 수 있다 소스코드 import heapq def dijkstra(start): heap = .. 2023. 5. 14.
[알고리즘] 유니온 파인드(Union-Find) 서론 union은 우리나라 말로 조합, 연합 이런 뜻도 있지만, 여기서는 합집합(union) 연산의 의미로 쓰이는 거 같다. union-find 알고리즘은 서로소인 집합을 집합론의 관점에서 보았을 때, ''' 집합 \(X(\neq\phi)\)의 임의의 부분집합 \(A,\,B,\,C\)에 대하여 다음이 모두 성립할 때, 집합 \(\mathcal{P}\)를 \(X\)의 분할(partition)이라고 한다. (a) \(A,\,B\in\mathcal{P}\wedge A\neq B\,\Rightarrow\,A\cap B=\phi\) (b) \(\displaystyle\bigcup_{C\in\mathcal{P}}{C}=X\) ''' union-find는 이러한 조건을 만족하는 집합들 중에서 각 원소가 속한 집합을 .. 2023. 5. 10.
[알고리즘]최소신장트리MST, Minimum Spanning Tree) Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 그래프에 있는 n개의 정점을 정확히 (n - 1)개의 간선으로 연결한다. ex) 통신네트워크 구축 MST란 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 Spanning Tree이므로 동일하게 n개의 정점을 정확히 (n - 1)개의 간선만 사용 ex) 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송시간 등을 최소로 구축하려는 경우 MST 구현 방법 Kruskal MST 알고리즘 탐욕적인 방법(greedy method)을 이용하여 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 조건 최소 비용의 간선으로 구성 사이클을 포함하지 않음 과.. 2023. 5. 10.

티스토리툴바