[ 알고리즘 개념 ] 프림 알고리즘 (Prim Algorithm) 프림 알고리즘 (Prim Algorithm) 최소 신장 트리 (Minimum Spanning Tree) 1. 개념 크루스칼 알고리즘과 마찬가지로 대표적인 최소 신장 트리 알고리즘으로써, 그리디 알고리즘으로 최적해를 보장하는 드문 사례이다. 최소 신장 트리에 대한 개념은 아래 글에 정리해두었다.https://codingexplore.tistory.com/61 [ 알고리즘 개념 ] 최소신장트리 (Minimum Spanning Tree) 최소신장트리 (Minimum Spanning Tree) 1. 개념 ▷ 신장트리란? - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 ( 큰 틀에서 트리에 포함되는 조건이다. ) - 즉, 누락된 노드 codingexplore.tistory.com 2. 동.. Algorithm/Algorithm Concepts 4년 전
[ 알고리즘 개념 ] 크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘 (Kruskal Algorithm) 1. 개념 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘이며, 그리디 알고리즘에 해당한다. 신장트리 및 최소 신장 트리에 대한 개념은 아래 글에 정리해두었다. https://codingexplore.tistory.com/61?category=886802 [ 알고리즘 개념 ] 최소신장트리 (Minimum Spanning Tree) 최소신장트리 (Minimum Spanning Tree) 1. 개념 ▷ 신장트리란? - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 ( 큰 틀에서 트리에 포함되는 조건이다. ) - 즉, 누락된 노드 codingexplore.tistory.com 2. 동작 과정 1) 간선을 가중치(Cost) 기준 .. Algorithm/Algorithm Concepts 4년 전
[ 알고리즘 개념 ] 최소신장트리 (Minimum Spanning Tree) 최소신장트리 (Minimum Spanning Tree) 1. 개념 ▷ 신장트리란? - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 ( 큰 틀에서 트리에 포함되는 조건이다. ) - 즉, 누락된 노드가 존재하거나 사이클이 존재하면 신장트리 조건 위배 - 아래 예시와 같이 한 그래프에 여러 신장트리가 존재할 수 있다. ▷ 최소신장트리란? - 최소한의 비용으로 구성되는 신장트리 예) N개의 도시가 있고, 이 도시 사이에 도로를 놓아 전체 도시가 연결되어야 하는데 이때, 최소 비용으로 연결 위 그림에서 두번째 신장 트리는 총 비용(Cost)이 11이므로 최소 신장 트리가 아니다. 세번째 신장 트리의 비용이 7로 더 작으므로 최소 신장 트리는 세번째이다. 최소 신장 트리 알고리즘에는 대표적.. Algorithm/Algorithm Concepts 4년 전
[ 알고리즘 개념 ] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 구현 - 파이썬(Python) 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 구현 - 파이썬(Python) ↓벨만 포드 알고리즘 에 대한 개념은 이전 게시글에 정리해두었다. codingexplore.tistory.com/57 [ 알고리즘 개념 ] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 1. 개념 벨만 포드 알고리즘은 간선의 가중치가 음의 값인 경우도 동작하는 최단 경로 알고리즘이다. 다익스트라 알고리즘은 0보다 작은 '음의 간선' 이 있 codingexplore.tistory.com 이번에는 파이썬 (Python) 으로 어떻게 벨만 포드 알고리즘을 구현할 것인가에 대한 것이다. 구현 - O(VE) : V 노드의 개수 E 간선의 .. Algorithm/Algorithm Concepts 4년 전
[ 알고리즘 개념 ] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 1. 개념 벨만 포드 알고리즘은 간선의 가중치가 음의 값인 경우도 동작하는 최단 경로 알고리즘이다. 다익스트라 알고리즘과 마찬가지로 시작 정점에서 다른 모든 정점으로의 최단 경로를 구하는 점에서 유사하다. 하지만 다익스트라 알고리즘은 0보다 작은 '음의 간선' 이 있으면 정상적으로 동작하지 않는다는 점에서 다르다. 하지만 벨만 포드는 시간복잡도가 O(VE) 이므로 다익스트라의 O(ElogV) 보다 비효율적이다. 따라서, 다익스트라를 사용할 수 있는 경우라면 그쪽을 사용하는 편이 효율성의 측면에서 더 낫다. 벨만 포드 알고리즘에서 '음의 간선' 이 있는 경우는 동작하지만, '음의 사이클' 이 존재하는 경우에는 동작하지 않는다는 점을 유의해야 .. Algorithm/Algorithm Concepts 4년 전
[ Baekjoon : python ] 백준 11404번 플로이드 - 플로이드 워셜 알고리즘 (Floyd WarshAlgorithm) [ BAEKJOON ONLINE JUDGE ] 11404 플로이드 _ Python 파이썬 1. 문제 입력 예시 출력 예시 5 14 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 3 5 10 3 1 8 1 4 2 5 1 7 3 4 2 5 2 4 0 2 3 1 4 12 0 15 2 5 8 5 0 1 1 10 7 13 0 3 7 4 10 6 0 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 아이디어 이 문제는 플로이.. Algorithm/Solved Problems 4년 전
[ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 구현 - 파이썬(Python) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 구현 - 파이썬(Python) ↓ 플로이드 워셜 알고리즘에 대한 개념은 이전 게시글에 정리해두었다. codingexplore.tistory.com/53 [ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 1. 개념 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점' 까지의 최단경로를 모두 구해야 하는 경우에 사용한다. '한 지점' 에서 나머지 codingexplore.tistory.com 이번에는 파이썬 (Python) 으로 어떻게 플로이드 워셜 알고리즘을 구현할 것인가에 대한 것이다. 구현 - O(N^3) INF .. Algorithm/Algorithm Concepts 4년 전
[ 알고리즘 개념 ] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 1. 개념 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점' 까지의 최단경로를 모두 구해야 하는 경우에 사용한다. '한 지점' 에서 나머지 지점의 최단경로를 구하는 다익스트라 알고리즘과는 용도가 사뭇 다르다. 다익스트라보다 소스 코드는 간결한 편이지만, 알고리즘 컨셉을 이해하는 것이 중요하다. 다익스트라 알고리즘에 대한 개념은 아래 글에 정리해두었다. codingexplore.tistory.com/51 [ 알고리즘 개념 ] 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 (Dijkstra Algorithm) 1. 개념 다익스트라 (Dijkstra) 최단경로 알고리즘은 그래프에서 여러 개의 node.. Algorithm/Algorithm Concepts 4년 전
