그래프이론 (4) 썸네일형 리스트형 [알고리즘] - 위상정렬 Topology Sort 정렬 알고리즘의 일종인 위상정렬 알고리즘은 '순서가 정해져 있는 일련의 작업을 수행할때' 사용하는 알고리즘이다. 즉 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 정렬하는 것을 위상정렬이라고 한다. 예를들면 선수과목을 생각하면 편하다. B라는 과목을 듣기 위해서 A라는 과목을 필수로 들어야 한다는 것과 동일하다. 즉 순서가 정해져있는 일련의 작업을 의미하게 된다. Toplogy Sort Algorithm 위상정렬 알고리즘은 다음 순서로 동작한다. - 진입차수가 0인 노드를 큐에 넣음 - 큐가 빌때까지 다음 과정을 반복 - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 - 새롭게 진입차수가 0이 된 노드를 큐에 넣음 만약 이 과정에서 모든 원소를 .. [알고리즘] 신장 트리, Kruskal 알고리즘 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 즉 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 신장트리는 코딩테스트에서 그리디 알고리즘 문제로 자주 출제되는 유형 중 하나라고 한다. 위 그림은 신장트리의 예시이며 모든 정점을 포함하면서 사이클이 존재하지 않는 구조를 띄고 있다. DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있으며 여러모양의 신장트리가 존재할 수 있다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간전으로 연결하여야 한다. 신장트리는 일반적으로 통신 네트워크를 구축할때 사용되기도 한다. Kruskal 알고리즘 신장트리에서 간선들의 가중치 합이 최소인 트리를 말한다. Minimum Spanning Tree .. [알고리즘] 서로소 집합 - Disjoint Sets 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 예를 들어 {1, 2}와 {3, 4}의 집합이 있다면 두 집합은 서로 서로소 관계이다. 만약 여기에 {2, 3} 의 관계를 나타낸다면 모두 서로소 관계가 아닌 것을 확인할 수 있다. 서로소 개념은 그래프 알고리즘에서 중요하게 사용되는 경우가 있어서 잘 알아두어야 한다. 그래서 서로소 집합 자료구조 (union-find 자료구조)는 서로소 부분 집합들로 나누어진 원소들을 처리하기 위한 자료구조라고 할 수 있다. 이는 union과 find 두 개의 연산자를 사용한다. union은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산을 담당하고 find 연산은 특정한 원소가 속한 집합을 찾는 연산을 담당한다. 서로소 집합 알고리즘 기본적으로.. [알고리즘] 그래프 이론 그래프 이론 코딩테스트에서 그래프이론을 활용하는 문제들은 대부분 난이도가 좀 있는 편이라고 생각한다. 지금까지 공부한 내용 중에서 DFS, BFS, 최단경로 알고리즘 모두 그래프를 이용하는 개념들이다. 알고리즘 문제에서 서로 다른 객체가 연결되어있다라는 내용이 내포되어있으면 가장 먼저 그래프 알고리즘 적용 여부를 판단해보아야 한다. 그래프 그래프는 정점과 간선으로 이루어진 자료구조 형태이다. 트리 또한 그래프의 일종이지만 트리는 방향성이 존재하고, 수직적인 관계를 가지고 있지만 그래프는 수직개념, 루트노드 등과 같은 개념이 없다. 즉 그래프는 네트워크 모델에 대한 관계를 나타낼때 효율적으로 사용될 수 있다. 대표적으로 지하철 노선도를 생각할 수 있다. 정점 - vertice : 노드라고 불리며 데이터가 .. 이전 1 다음
