이번 포스트에서는 위상정렬 알고리즘에 대해 살펴보자.위상정렬 알고리즘 문제제시https://www.acmicpc.net/problem/14567  위상정렬 알고리즘이란?위상정렬(位相整列:  Topological Sorting)이란 노드 간의 위치(선-후관계)에 따라 모든 정점들을 배열하는 작업을 말한다. 주로 업무의 일정을 일이 진행되어야 할 순서에 따라 배치하기 위해 사용되는 알고리즘이다. 대표적으로 과목들간의 선수관계에 따른 수강 계획을 작성한다든가 게임에서 어떤 빌딩을 생성하기 위한 테크트리를 떠올리면 쉽다.대부분의 위상 정렬 문제들은 선-후 관계에 위배되지 않는 경우 중 하나를 출력하는 문제들이다.그래프 요소들이 정렬되기 위해서는 당연히 명확한 순서가 있어야 한다. 따라서 위상 정렬은 DAG(di..

이번 포스트에서는 서로소 집합(disjoint set)에 대해서 살펴보자.  서로소 집합 문제제시https://www.acmicpc.net/problem/2606 서로소 집합이란?서로소 집합(disjoint set)이란 상호 배타집합이라고도 불리며 서로 중복 포함된 원소가 없는 집합 즉 교집합이 없는 상태의 집합을 의미한다. 서로소 집합은 집합에 속한 하나의 특정 멤버를 통해 각 직합을 구분하는데 이를 집합의 대표자(representative)라고 한다.서로소 집합을 찾기 위한 알고리즘을 union-find 알고리즘이라고도 하는데 일반적으로 makeSet, findSet, union 3가지 메서드로 구성되기 때문이다. 서로소 집합의 연산과 표현서로소 집합을 표현할 때는 연결 리스트를 활용하거나 배열을 이..

이번 시간에는 MST를 구하는 두 번째 알고리즘으로 Prim에 대해서 살펴보자. Prim 알고리즘 알고리즘 개요Prim은 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 구성하는 방식이다. 따라서 Kruskal과 달리 정점 중심의 알고리즘이다.Prim은 서로 소인 두 개의 집합 즉 [MST 집합]과 [비 MST 집합]으로 정점들을 관리한다.(그렇다고 union find 를 쓴다는 이야기는 아니다.) 여기서 [MST 집합]은 MST를 구성하고 있는 정점들의 집합이고 [비 MST 집합]은 아직 MST를 구성하고 있지 않은 정점들의 집합이다. 우리는 [비 MST] 집합에서 하나씩 정점들을 선택해서 MST 집합을 완성해나가는 과정이다.Prim의 기본 동작은 다음과 같다.어차피 모든 정점은 MST ..

이번 포스트에서는 MST를 구하기 위한 Kruskal 알고리즘에 대해 살펴보자. Kruskal 알고리즘 알고리즘 개요크루스칼 알고리즘은 간선을 중심으로 MST를 구하는 알고리즘이다. 어차피 MST는 트리이므로 Circle을 만들지 않으면서 비용이 작은 간선들을 계속해서 연결하다보면 MST가 구성되는 특징을 이용한다.Kruskal의 기본 동작은 다음과 같다.모든 간선을 가중치에 따라 오름차순으로 정렬한다.간선을 하나씩 연결해간다. - 이 과정에서 Circle이 발생하면 그 간선은 버리고 다음 간선을 선택한다.트리이므로 N-1개의 간선이 선택되면 종료한다. 알고리즘 전개 절차  기본 코드Kruskal은 최소 비용의 간선들을 연결하는 과정에서 Circle을 판별하기 위해 Union-Find 자료구조를 사용한다..

이번 포스트에서는 MST의 개요에 대해서 알아보자. MST 문제 제시https://www.acmicpc.net/problem/6497  키워드: 모든 집들을 연결, 절약할 수 있는 최대 액수(최소 비용) MST(Minimum Spanning Tree) 개념먼저 Span이란 교각과 교각 사이의 거리를 말한다. 즉 그래프에서는 정점과 정점을 잊는 무향의 간선을 말하며 이 span의 거리는 일반적으로 가중치를 나타낸다.Spanning Tree(신장 트리)란 말 그대로 span으로 이뤄진 트리이다. span이니까 간선을 의미한다는걸 알겠고 거기에 tree의 속성이 추가된 것이다. tree란 circle을 이루지 않는 특징이 있다. 따라서 Spanning Tree는 다음과 같이 정의할 수 있다.N개의 정점으로 이..