반응형 topological sort2 [C/C++] 백준 #2623 음악프로그램(위상정렬) 이번 문제는 그래프 이론 중 위상정렬을 이용한 문제입니다.위상정렬은 일의 선후 관계가 주어지는 경우 선후관계를 맞추어서 하나의 리스트로 만들게 됩니다.하지만 그래프의 노드 중 연결되지 않은 노드가 있거나 순환(cycle)이 존재하면 답이 없을 수 있습니다. 음악프로그램 문제는 문제 자체는 위상정렬과 동떨어져 보일 수 있지만, 문제를 잘 해석해서 이 문제가 위상정렬 문제임을 알아내는 것이 중요합니다. 그렇지 않다면, 꽤 어려운 문제가 될 수 있습니다. 문제의 출처입니다.https://www.acmicpc.net/problem/2623 음악 프로그램에서 AD가 여러명이라고 하지만, 이 여러명의 AD들이 가져온 순서들을 병합(merge)하면 하나의 큰 유향 그래프(directed graph)가 됩니다. .. 2024. 5. 10. [C/C++] 백준 #2056 작업(위상정렬) https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 이번 문제는 선행작업과 후행작업이 있을 때, 전체 작업시간이 얼마나 걸릴 것인지 판단하는 것입니다. 소프트웨어 공학에서 자주 발생하는 일입니다. 소프트웨어 공학에서도 선행작업과 후행작업이 있는 경우 작업 인력을 무한정 투입할 경우 마칠 수 있는 최소 시간을 구하게 됩니다. 이와 같이 작업의 선후가 있는 경우에 위상정렬을 사용하게 됩니다. 위상절렬은 작업의 선후에 따라서 정렬을 하는 것이지.. 2023. 3. 23. 이전 1 다음 728x90
