Union Find (합집합 찾기) MST - 1 정말 오랜만에 포스팅이다. MST 알고리즘 문제를 풀던 도중 생각나서 포스팅 하게 됐다. 매주 주말마다 알고리즘 개념 정리를 하려고 하는데 계속 실패하는 것 같다... ㅎㅎ;; 오늘 다뤄볼 주제는 MST, 최소 신장 트리 문제를 해결하기 위한 기본 베이스인 Union Find이다. 최소 신장 트리 문제를 해결하기 위한 방법에는 대표적으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 존재한다. Union FInd는 크루스칼 알고리즘의 핵심이라고 말할 수 있다. 그럼 Union Find가 무엇인지 알아보자. Union Find는 말 그대로 Union, 집합을 찾는 알고리즘이다. 그래프 정보가 주어졌을 때 이들 간의 관계를 알아볼 수 있다. 바로 예시..
Floyd Warshall (플루이드 와샬) 최단 경로 탐색 - 3 오랜만에 포스팅이다. 주말마다 한 개씩은 쓸라했는데 주말에 좀 바빠서 못썼다... 어제 백준에서 플루이드 와샬 문제를 풀고 갑자기 블로그 포스팅이 생각나서 쓰게 됐다! 다익스트라, 벨만 포드에 이은 플루이드 와샬 알고리즘 최단 경로 탐색 카테고리의 마지막 내용이다. 다익스트라, 벨만 포드는 특정 노드에서 다른 노드까지의 최단 경로를 탐색해준다. 조금 생각을 바꿔서 모든 노드에서 다른 노드까지의 최단 경로를 탐색하려면 어떻게 해야할까? 우선 기존에 배웠던 다익스트라와 벨만 포드를 사용하여 탐색할 수 있다. 다익스트라에서 입력 값으로 넣어주는 src, 즉 출발 노드를 모든 노드로 설정하면 된다. 그만큼 반복문을 돌아야하기에 시간복잡도는 N만..
Bellman Ford (벨만 포드) 최단 경로 탐색 - 2 오늘은 지난번 다익스트라에 이어 최단 경로를 탐색하는 알고리즘을 정리하려고 한다. 지난번 다익스트라 포스팅에서 다익스트라는 음의 사이클이 있는 그래프에서는 사용이 불가능하다고 하였다. 그 이유는 무엇일까? 우선, 다음과 같은 그래프의 시작 정점이 A라고 했을 때의 최단 경로를 구해보자. [예상 결과] A : 0 B : -4 C : 3 D : -7 E : 1 F : -3 [실제 결과] 시작 정점에서 이상한 값이 출력되는 것을 볼 수 있다. 다른 예시를 보자. [예상 결과] A : 0 B : 2 ( 재방문을 하지 않는다고 가정) C : 5 D : 1 E : 3 [실제 결과] 역시, E 정점에서 이상한 값이 출력되는 것을 볼 수 있다. 이유가 뭘까?..
Dijsktra (다익스트라) 최단 경로 탐색 - 1 정말 오랜만에 포스팅이다. 원래 목표대로 진행했으면 개강을 하기 전에 DP까지 포스팅을 했어야하는데 요새 조금 바빴다...(사실 의욕이 없던걸 수도...) 아무튼 이번 3-1 과목에 알고리즘 응용이라는 과목을 수강하는데 작년에는 딥러닝과 관련하여 수업했다고해서 신청했는데 이번에 교수님이 바뀌면서 정말 알고리즘에 대해 학습하는 수업이 되어버렸다. 살짝 아쉬웠지만 강의계획서를 보니 2-2 알고리즘 수업과 거의 비슷해서? 학기 초에 미리미리 정리해두려고 한다. 서론이 길었다. 다익스트라는 최단 경로를 탐색하는 알고리즘이다. 다음과 같은 그래프의 최단 경로를 탐색해보자. graph 변수에 연결된 정점과 가중치가 저장되어 있다고 본다. graph[1] = [2..
DFS(Depth-Find-Search) 깊이 우선 탐색 지난 시간 BFS에 이어 오늘은 DFS에 대해 알아보려고 한다. DFS는 Depth-Find-Search로 깊이 우선 탐색이다. BFS와 다르게 DFS는 깊이를 우선적으로 탐색한다. 즉 최대 깊이까지 재귀적으로 이동한 후 최대 깊이에 도달한 경우 옆으로 이동한다. 또한 BFS에서는 Queue를 사용했다면 DFS에서는 Stack을 사용한다. 이 Stack에 저장된 값이 우리가 원하는 DFS의 탐색 순서이다. 알고리즘 동작 방식 다음과 같다. 1. 특정 정점이 아직 방문하지 않은 정점인 경우 이를 방문처리 해준다. 2. 해당 정점과 연결된 다른 정점에 대해 위 과정을 반복한다. 다음과 같은 그래프가 주어졌을 때 DFS를 적용해보자. ① 시작 정점을 8..
BFS(Breath-Find-Search) 너비 우선 탐색 그래프의 탐색 방법 중 하나의 BFS에 대해서 살펴보려고 한다. BFS는 말 그대로 너비 우선 탐색, 즉 특정 Vertice에서 가장 가까운 Vertice부터 탐색한다는 뜻이다. 우선 BFS를 사용하기 위해서는 Queue가 필요하다. Stack, Queue, Heap에 대해서는 나중에 자세히 설명하기로 하고 Queue에 대해 간단하게 설명하자면 FIFO(First in First out - 선입선출)으로 동작하는 자료구조이다. 위에서도 말했듯이 BFS의 가장 큰 개념은 가까운 정점을 방문하되, 아직 방문하지 않은 정점인 경우 방문 리스트에 정점을 저장하면 된다. 이 방문 리스트가 우리가 원하는 최종적인 BFS의 탐색 순서이다. 알고리즘 동작 방식..
