Algorithm(38)
-
[알고리즘][Graph] 최단 경로(Shortest Path) #2 최단 경로 문제, Dijkstra 알고리즘
학습목표 1. Bellman-Ford 알고리즘의 문제점 2. Dijkstra 알고리즘에 대해서 학습 3. Dijkstra 알고리즘의 수행과정에 대해서 학습 4. Java 언어 기반 Dijkstra 알고리즘 구현 5. Dijkstra 알고리즘의 시간복잡도에 대해서 학습 1. Bellman-Ford 알고리즘의 문제점 Bellman-Ford 알고리즘의 문제점은 특정한 노드의 distance 값이 갱신될때마다 그와 연결된 노드들도 distance 값을 갱신해야 되는 문제점을 가지고 있습니다. 위의 그림과 같이 노드 V의 distance가 변경될때마다 노드 V와 연결된 노드들도 distance를 갱신해주어야 합니다. 위 문제를 해결하기 위해서는 Relaxtion 연산을 줄일 필요가 있습니다. Relaxtion 연..
2022.02.22 -
[알고리즘][Graph] 최단 경로(Shortest Path) #1 최단 경로 문제, Bellman-Ford 알고리즘
학습목표 1. 최단 경로의 개념에 대해서 학습 2. 최단 경로 문제의 유형과 특징에 대해서 학습 3. Single-Source 최단 경로 문제에 대해서 학습 4. Bellman-Ford 알고리즘에 대해서 학습 5. Java언어 기반 Bellman-Ford 알고리즘 구현 1. 최단 경로란 무엇인가? 그래프에서 최단 경로란 방향, 무방향 그래프 상관없이 특정한 노드 u,v가 주어졌을때 u노드부터 시작하여 v노드까지 가는 경로중에서 가중치의 합이 최소인 경로를 최단 경로라고 합니다. 이를 기호로 표시하면 δ(u,v)로 표시하기도 합니다. 위 그림에서 노드 A에서 출발하여 노드 F까지 도착하는 여러 경로 중에서 최단 경로는 A->C->E->D->F인 것을 알수 있습니다. 2. 최단 경로 문제의 유형 Single..
2022.02.21 -
[알고리즘][Graph] 최소 비용 신장 트리 #4 프림(Prim's) 알고리즘의 개념과 수행과정
학습목표 1. 프림(Prim's) 알고리즘이란 무엇인지 학습 2. 프림 알고리즘의 수행과정에 대해서 학습 3. Java언어 기반 프림 알고리즘 구현을 수행 3. 프림 알고리즘의 시간복잡도에 대해서 학습 1. 프림(Prim's) 알고리즘이란 무엇인가? 프림 알고리즘은 최소 비용 신장 트리(Minimum Spanning Tree, MST)를 탐색하기 위해 사용되는 알고리즘입니다. 프림 알고리즘은 임의의 노드에서 시작하여 출발 노드를 포함하는 트리(MST)를 점점 키워갑니다. 그리고 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 간선들 중 가장 가중치가 작은 에지를 선택하는 알고리즘입니다. 2. 프림(Prim's) 알고리즘의 수행과정 프림 알고리즘의 수행과정은 다음과 같습니다. 그래프의..
2022.02.15 -
[알고리즘][Graph] 최소 비용 신장 트리 #3 크루스칼(Kruskal) 알고리즘의 싸이클 검사와 구현
학습목표 1. 싸이클 검사의 수행과정을 학습 2. Java언어 기반 크루스칼 알고리즘 구현 학습 3. 크루스칼 알고리즘의 시간복잡도 계산을 학습 1. 싸이클 검사 크루스칼 알고리즘을 수행하게되면 에지(edge)들중 가중치(weight)가 최소인 에지들을 결과 배열에 넣게됩니다. 이때 에지들을 넣기전에 싸이클을 검사해야 합니다. 싸이클이란 그래프의 특정 노드에서 출발하여 방향(edge)을 따라 다시 출발한 노드로 올 수 있는 상황을 싸이클이 발생하였다고 합니다. 최소 신장 트리(Minimum Spanning Tree)에서는 싸이클이 존재해서는 안되기 때문에 에지들을 정하기 전에 싸이클 검사를 수행하여야 합니다. 싸이클이 존재하는지 탐색하는 방법에는 Union-Find 알고리즘을 사용하여 탐색할 수 있습니다..
2022.02.09 -
[알고리즘][Graph] Disjoint Set #2 Union By Rank와 Path Compression
학습목표 1. 기존 Union-Find 알고리즘의 문제점을 파악 2. Union-Find의 O(h)을 O(log n)으로 변경하는 union by rank와 path compression에 대해서 학습 이전글 https://yonghwankim-dev.tistory.com/235 [알고리즘][Graph] Disjoint Set #1 무방향 그래프에서 싸이클 탐색 학습목표 1. Disjoint Set 자료구조에 대해서 학습 2. Disjoint Set 자료구조를 이용하여 그래프에 싸이클이 있는지 검사 1. Disjoint-Set 자료구조란 무엇인가? Disjoint-Set 자료구조는 서로 중복되지 않는 부 yonghwankim-dev.tistory.com 1. 기존 Union-Find 알고리즘의 문제점 이..
2022.02.08 -
[알고리즘][Graph] Disjoint Set #1 무방향 그래프에서 싸이클 탐색
학습목표 1. Disjoint Set 자료구조에 대해서 학습 2. Disjoint Set 자료구조를 이용하여 그래프에 싸이클이 있는지 검사 1. Disjoint-Set 자료구조란 무엇인가? Disjoint-Set 자료구조는 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조입니다. 예를 들어 집합 {1,2,3}과 집합 {4,5}는 서로 중복되는 원소가 없으므로 Disjoint-Set입니다. 2. Union-Find 알고리즘 수행과정 union-find 알고리즘은 disjoint-set 자료구조에 대해 2가지 유용한 연산을 수행하는 알고리즘입니다. Find : 특정 원소가 어느 부분집합인지 탐색합니다. Find 기능은 두개의 원소가 서로 같은 부분집합인지 확인하는데 사..
2022.02.08