분류 전체보기37 [알고리즘] 다익스트라 vs 크루스칼/프림 차이를 알아보자 다익스트라(dijkstra) vs 크루스칼(kruskal) + 프림(prim) 앞선 포스팅에서 다익스트라와 크루스칼/프림 알고리즘에 대하여 설명했다. 다익스트라는 최단 경로의 해를 구하는 목적이고, 크루스칼과 프림은 MST(최소 신장 트리) 문제를 해결하는 목적이다. 비슷한 그래프 알고리즘 개념이라 혼동이 올 수 있어 세가지 알고리즘을 비교해 본다. 다익스트라 크루스칼/프림 용도 최단 경로 탐색 최소 신장 트리 해결 상세 설명 하나의 정점에서 다른 정점(들) 까지의 최단 경로를 탐색 모든 노드를 최소한의 비용으로 방문하는 간선을 탐색 특징 두 정점 간 최단 경로(최소 가중치 간선)만 선택 두 정점 간 최단 경로(간선)가 아니더라도 선택 가능 ( 두 정점 간의 최단 경로를 보장하지 않음 ) 구현 방법 he.. 2023. 1. 17. [알고리즘] 파이썬 프림(prim) & 크루스칼(kruskal) 예제 및 비교 MST(최소신장트리) 문제를 위한 프림 & 크루스칼 알고리즘 - 프림과 크루스칼은 MST(최소 신장 트리) 문제 해결을 위한 알고리즘이다. - MST(최소 신장 트리)란 그래프에서 모든 노드를 연결할때 간선의 가중치 합이 최소가 되는 경우를 말한다. - 최단 경로 문제와 다른 점은 한 노드에서 다른 모든 노드까지의 거리가 최소가 되는 것이 아니라, 모든 노드를 연결했을 때 최소가 되는 경우를 찾는 것이다. - 따라서 특정 노드에서 다른 노드로 가는 간선이 local minimum은 아닐 수 있지만, 결국 global minimum을 위한 것이다. 프림(prim) 알고리즘? - 시작노드를 선정하여 시작노드부터 확보된 모든 간선 중 순환을 피해 최소 간선을 연결하는 방식. - 모든 노드가 직접 연결되지 않아.. 2023. 1. 15. [알고리즘] 파이썬 다익스트라(Dijkstra) 최단경로 문제 예 다익스트라 알고리즘 - 다익스트라는 최단경로를 구하는 알고리즘 중 가장 많이 사용되는 알고리즘 중 하나이다. - 파이썬에서는 heapq를 활용하여 비교적 쉽게 구현할 수 있다. - 노드(vertex)와 간선(edges)으로 이루어진 그래프에서 단방향 혹은 양방향 최단 경로를 구할 때 사용한다. - 간선은 음수를 가질 수 없다는 조건이 있어야 사용 가능하다. ( 간선의 가중치가 음수인 경우 사용 불가 ) - 특정 노드에서 다른 노드로 갈 때, 가능한 모든 경우의 간선으로 방문하여 노드 간 최소 거리를 찾는다. → 한번 방문하여 노드 사이의 거리를 구했어도, 다른 더 짧은 경로가 있을 수 있으므로 검사한다. → 노드로 들어오는 모든 경로를 탐색했다면, 그중 최소값을 두 노드간 거리로 선택한다. 예제 - 보통.. 2023. 1. 15. [알고리즘] 파이썬 DFS/BFS 정리 및 예제 풀이 코딩테스트 기본 문제 DFS/BFS - DFS와 BFS는 코딩테스트 단골문제로 코딩테스트를 준비하는 사람이라면 반드시 알고 있어야 한다. - DFS와 BFS 모두 그래프 탐색 기법으로, 완전 탐색 알고리즘(Brute Force)의 일종이다. - 완전 탐색 알고리즘이므로, 시간의 제약이 있는 경우 DP나 heap 등을 이용해 시간을 줄여야 한다. - SWEA 기준 3~4 level(advanced등급) 시험에서는 DFS/BFS만 가지고 해결가능한 문제가 주로 나온다. - SWEA 5 level 이상(pro 등급) 시험에서는 DFS/BFS + DP 및 heap 등 추가 기법을 활용하는 문제가 주로 나온다. DFS( Depth Firsrt Search : 깊이 우선 탐색 ) - DFS는 그래프 탐색 기법으로 .. 2023. 1. 15. 이전 1 2 3 4 5 6 7 8 ··· 10 다음