알고리즘 3
[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 그래프에서 정점 사이의 최단 경로를 찾는 알고리즘 입니다. 프림 알고리즘과 동작방식이 비슷하지만 다익스트라 알고리즘은 시작 정점에서 정점 V 까지의 경로의 길이를 기준으로 최단 경로를 연결합니다. (단 가중치가 음수인 경우 사용할 수 없습니다.) 다익스트라 알고리즘은 다음과 같은 원리로 동작합니다. 시작 정점으로부터 각 정점까지의 경로의 길이를 저장할 배열을 만들고 모든 정점을 ∞(무한대)으로 초기화 시작 정점의 경로의 길이를 0으로 초기화하고 시작 정점을 최단 경로에 추가 최단 경로에 추가된 정점의 인접한 정점을 확인해서 경로의 길이를 갱신하고 최단 경로에 추가. (단 추가하려는 정점이 이미 최단 경로 안에 존재할 경우 경로의..
[알고리즘] 최소 신장 트리(Minimum Spanning Tree)
최소 신장 트리(Minimum Spanning Tree) 신장 트리(Spanning Tree)는 그래프 내에 있는 모든 정점을 연결하고 사이클이 없는 그래프를 의미합니다. n개의 정점이 있다면 신장 트리의 간선 수는 n-1개가 됩니다. 최소 신장 트리는 각 간선이 가지고 있는 가중치의 합이 최소가 되는 신장 트리입니다. 가중치는 거리, 비용, 시간 등 여러가지로 응용할 수 있습니다. 최소 신장 트리의 대표적인 알고리즘으로는 프림 알고리즘(Prim’s Algorithm)과 크루스칼 알고리즘(Kruskal’s Algorithm)이 있습니다. 프림 알고리즘(Prim’s Algorithm) 프림 알고리즘은 로버트 프림(Robert C. Prim)이 만든 최소 신장 트리 알고리즘 입니다. 프림 알고리즘은 최소 신..
[알고리즘] 그래프(Graph)
그래프 정의 그래프는 정점(Vertex)의 집합과 간선(Edge)의 집합으로 이루어진 자료구조입니다. 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G = (V, E) 입니다. 정점은 위치를 의미하고, 간선은 정점과 정점을 연결하는 선을 의미합니다. 간선으로 연결되어 있는 두 정점을 가리켜 서로 인접(adjacent)해 있다고 표현합니다. 인접한 두 정점은 경로를 형성하기도 하는데 위 그림을 보면 1, 2, 3, 4 가 경로를 형성합니다. 경로 1, 2, 3, 4 사이에는 간선이 (1, 2), (2, 3), (3, 4) 3개가 있으므로 길이는 3이 됩니다. 경로가 정점 하나를 두 번 이상 거치게 된다면 그 경로는 사이클(Cycle)이 있다고 표현합니다. 위 그림에서 1, 2, 3 경로가..