반응형 Algorithm/알고리즘2 위상 정렬 알고리즘 위상 정렬 (topological sorting) 방향 그래프에서 노드의 방문 순서를 찾는 알고리즘이다. 우리 일상에서 접할 수 있는 위상정렬의 한 예는 수업 커리큘럼이 있다. 내가 나온 학교의 예를 들면 c프로그래밍 > 고급 c 프로그래밍 > 자료구조 > 알고리즘 순으로 수강을 할 수있다. 즉 앞의 과목들은 선수과목이 되는것이다. 위 순서를 어기고선 수강을 할 수 없는데 이러한 순서를 찾는것이 위상정렬 알고리즘이다. 위상 정렬 알고리즘을 사용하기 위해선 사이클이 없는 방향 그래프여야 한다. 즉 A > B > C > A 로 돌아가는 방향을 갖는 그래프이면 안된다. 알고리즘은 간단하다. 1차원 배열로 그래프를 구현한다. 진입차수가 0인 그래프를 큐에 넣는다. 큐를 빼면서 해당 노드의 다음 노드의 진입차수를.. 2024. 2. 26. 분리 집합 (Disjoint Set) : Union-Find 알고리즘 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 위 문제를 풀다가 몰라서 정리하고 간다. Union-Find 알고리즘은 분리 집합(Disjoint-set) 자료구조를 구현하는 데 사용된다. Union: 두 개의 집합을 하나로 합치는 연산. 두 집합을 합치기 위해 루트를 찾아서 하나의 집합으로 만듦. Find: 주어진 원소가 주어진 집합의 루트를 찾는 연산. 이 연산을 통해 두 원소가 같은 집합에 속해 있는지.. 2023. 9. 5. 이전 1 다음 반응형
