위상 정렬3 [백준 C++] 1766번: 문제집 1. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 2. 알고리즘 분류 자료 구조 그래프 이론 우선순위 큐 위상 정렬 방향 비순환 그래프 3. 소스 코드 #include #include #include #include #define MAX_N 32001 using namespace std; int N, M; int visited[MAX_N]; int inDegree[MAX_N]; vector graph[MA.. 2024. 4. 11. [백준 C++] 2252번: 줄 세우기 1. 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2. 알고리즘 분류 그래프 이론 위상 정렬 3. 소스 코드 Key Point) 1. 그래프를 이용하여 학생 순서를 정리한다. 2. '위상 정렬'을 사용하여 그래프 순서대로 값을 정렬한다. #include #include #include #define MAX_N 32001 using namespace std; int N, M; int visite.. 2023. 10. 3. [알고리즘] 위상 정렬(Topological Sorting) 1. 개요 및 대표 문제 1. 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘 2. 사이클이 없는 방향 그래프(Direct Acyclic Graph)에서만 수행 3. 시간 복잡도 = O(V + E) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 2. 위상 정렬의 대표 예시 위의 이미지처럼 작업의 순서가 정해져 있을 때 작업을 정렬해주는 알고리즘이 바로 '위상 정렬'이다. .. 2023. 10. 2. 이전 1 다음
