Algorithm/기타 그래프 이론
위상정렬(Topology Sort) 이론
위상정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 이 알고리즘이 왜 필요할까? 어느 문제에서 사용할까? 예를들어, 대학교 커리큘럼처럼 선수과목이 있는 과목이 있다고 가정해보자. 고급 알고리즘을 수강하기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘의 순서로 수강해야한다. 자료구조 -> 고급알고리즘 -> 알고리즘 의 순서로는 수강할 수 없다. 이와같이, 방향그래프의 방향성에 거스르지 않도록 나열해야하는 문제에서 위상정렬을 사용할 수 있다. 진입차수와 진출차수 위상정렬을 구현하기 위해서 진입차수와 진출차수의 개념을 짚고 넘어가야 한다. 진입차수 : 특정한 노드로 들어오는 간선의 개수 진출차수 : 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 구현 ..
신장트리와 크루스칼 알고리즘
신장트리 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 부분 그래프 그렇다면, 신장트리가 왜 필요할까? 어느 문제에서 쓰일 수 있을까? 예를들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 최소비용으로 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. N개의 도시를 다 연결하기 위해서 모든 노드가 포함되어야 하고 최소비용으로 연결하기 위해서 사이클이 존재하지 않고, 최소비용의 간선만 존재해야 한다. 그러면 주어진 데이터에서 신장트리를 어떻게 만들 수 있을까? 크루스칼 알고리즘 대표적인 최소 신장 트리를 구할 수 있는 알고리즘이다. 구현방법 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다..
Union Find 자료구조 이론
Union Find 자료구조 ( 서로소 집합 자료구조 ) 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 여기서 집합은 트리구조를 의미하고, 서로소 부분 집합은 루트노드가 다른 것을 의미한다. 그래서, Union 각자 서로소인 부분 집합을 하나의 집합으로 합치는 연산. ex) union(1, 4) 이면 1의 루트노드와 4의 루트노드를 비교해서 더 큰 루트노드의 부모를 작은 루트노드로 세팅한다. 주의 : 해당 노드가 아닌 루트노드의 부모를 세팅하는 것이다. Find 어떤 원소가 어떤 집합에 속해있는지 (루트노드가 무엇인지) 알려주는 연산 ex) 루트를 찾을 때 까지 (부모가 자기자신인 경우) 부모를 재귀적으로 호출한다. 이라고 보면된다. 동작방식을 그림으로 살펴보자 동작방식 이렇게 ..