이것저것 코딩하는 블로그

1. Minimum Spanning Tree (MST) MST란, 트리가 주어져 있을 때 모든 노드들이 연결되어 있으면서 가중치의 합이 최소인 spanning tree (tree의 일부분, 부분집합 개념으로 생각하면 된다) 이다. 단, 이는 cycle을 포함해서는 안된다. Spanning tree의 정의 자체가 cycle을 포함하지 않는 것이기 때문이다. 이를 찾아주는 알고리즘이 크루스칼 알고리즘이다. 2. 크루스칼 알고리즘 이는 union-find를 이용하여 MST를 찾아준다. union-find에 대한 글은 다음 링크를 참고하자. https://codinglilly.tistory.com/32 [Algorithm] Union-Find 1. Union-Find란? 여러 개의 원소가 있고, 여러 개의 집합..

1. Union-Find란? 여러 개의 원소가 있고, 여러 개의 집합이 있다고 가정하자. 특정 원소가 어느 집합에 속해있는지 확인하고, 특정 집합을 합쳐야 할때 해당 알고리즘을 사용한다. 집합에 속하는 것을 한 원소를 대표로 하여 자식 노드로 이어줌으로써 집합을 구현한다. 1) Union 두 집합을 합치는 연산이다. 두 집합에 속하는 자식 노드들을 모두 찾은 후, 한 집합의 부모 노드를 다른 집합의 자식 노드로 하면 모든 원소가 하나의 부모 노드로 이어지게 된다. 코드로 표현하자면, 부분집합 x의 조상(루트)을 부모로 하고 y를 그 밑에 붙인다고 생각하면, uf(find[x]) = uf(find[y]) 가 된다. 2) Find 집합에 속한 원소를 찾는 연산이다. 부모 노드에 대해 연결된 자식 노드를 찾고..

1. 플로이드-워셜 알고리즘이란? 다익스트라 알고리즘은 특정 시작점이 있을 때만 사용할 수 있다. 따라서 모든 지점의 거리를 구하는 데는 번거로울 수 있다(모든 점들에 대해 다익스트라 알고리즘을 수행해야 한다). 이 때 사용하는 것이 플로이드-워셜 알고리즘이다. 기본 아이디어는 다익스트라와 유사하다. 단, 이를 모든 노드가 시작점일 때를 고려하여 수행할 뿐이다. A에서 B로 가는 경로보다 A에서 X를 거쳐 B로 가는 경로가 짧다면 최단 경로를 갱신하는 방식이다. 그러나 애초에 모든 점을 방문해야 하므로 다익스트라 알고리즘에 비해 느리다. 따라서 지점의 갯수가 적다면 다익스트라를 여러 번 돌리는 게 나을 수 있다. 코드를 보며 알아보자. 2. 구현 n = int(input()) graph = [] dist..

1. 다익스트라 알고리즘 다익스트라 알고리즘은 가중치가 있는 그래프에서, 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘이다. 이는 특정 지점까지의 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리 라는 아이디어를 기반으로 한다. 과정을 살펴보면 다음과 같다. 1) 거리 배열을 최댓값으로 초기화하고, 출발지의 값만 0으로 설정한다. 2) 현재 방문하지 않은 정점 중 가장 거리 값이 작은 지점을 선택한다. 3) 해당 지점과 인접한 지점들의 거리를 갱신한다. 4) 모든 지점이 선택될 때 까지, 2와 3을 반복한다. 다음 그래프를 통해 살펴보자. 자세한 설명은 다음 링크를 참고하면 된다. 많은 도움을 받았다. https://www.codetree.ai/missions..

1. BFS란? BFS는 너비 우선 탐색으로, 그래프를 층별로 탐색하는 것이다. 자세히 얘기하자면, 한 노드를 방문했을 때 그 노드의 모든 자식 노드를 방문해야 다음 노드로 갈 수 있다. 이 과정을 루트 노드부터 시작해서 모든 리프 노드를 방문할 때까지 반복한다. DFS와 달리 모든 리프 노드를 방문했다면 탐색이 끝난 것이므로 (맨 아래층에 있으므로) 종료한다. 예제를 통해 살펴보자. 다음과 같은 그래프를 너비 우선 탐색으로 탐색하고자 한다. 먼저 루트 노드인 9를 방문한다. 이후 9의 자식 노드인 8과 6을 방문한다. 자식 노드를 방문했으면, 자식 노드 중 가장 왼쪽으로 이동해 그 노드의 자식들을 모두 방문한다. 여기서는 5와 2가 된다. 이후 오른쪽 노드로 이동해 자식을 방문한다. 여기서는 1이 된다..

1. DFS란? 깊이 우선 탐색(DFS)는 의미 그대로 깊이를 우선으로 하여 탐색하는 것이다. 자세히 얘기하자면, 루트 노드에서 시작해서 자식 노드로 이동한다 (보통 왼쪽 노드로 이동한다). 이동한 자식 노드에서 다시 자식 노드로 이동한다. 이 과정을 자식 노드가 없을 때까지 (리프 노드에 갈 때까지) 반복한다. 리프 노드에 도달하면, 리프 노드의 부모 노드로 가서 다시 오른쪽 자식을 방문한다. 오른쪽 자식에서 위에서 했던 과정을 반복한다. 이 재귀적인 방문을 탐방이라고 하겠다. 이렇게 모든 노드를 방문할 때까지 탐방을 완료하면 search가 끝난다. 그래프를 예를 들어보자. 위와 같은 그래프가 있다고 할때, 깊이 우선 탐색으로 탐색해보자. 루트에서 왼쪽으로 계속 이동하며 리프 노드가 나올 때까지 가므로..