반응형 위상정렬5 [C/C++] 백준 #2056 작업(위상정렬) https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 이번 문제는 선행작업과 후행작업이 있을 때, 전체 작업시간이 얼마나 걸릴 것인지 판단하는 것입니다. 소프트웨어 공학에서 자주 발생하는 일입니다. 소프트웨어 공학에서도 선행작업과 후행작업이 있는 경우 작업 인력을 무한정 투입할 경우 마칠 수 있는 최소 시간을 구하게 됩니다. 이와 같이 작업의 선후가 있는 경우에 위상정렬을 사용하게 됩니다. 위상절렬은 작업의 선후에 따라서 정렬을 하는 것이지.. 2023. 3. 23. [C/C++] 백준 #1766 문제집(위상정렬) 이번 문제는 일을 처리하는데 있어서 우선순위가 주어진 경우 그것을 해결하는 방법입니다. 1. N개의 문제는 반드시 풀어야 한다. 2. 먼저 푸는 것이 좋은 문제가 있는 경우에는 더 쉬운 문제를 먼저 풀어야 한다. 3. 쉬운 문제가 있다면, 쉬운 문제를 먼저 풀어야 한다. 1번 조건과 2번 조건만을 보면 위상 정렬입니다. 3번 조건은 위상정렬을 할 때, 인입간선이 없는 것들중에 문제 번호가 적은 것을 우선 선택할 수 있도록, 문제 번호대로 우선순위 큐를 작성하면 됩니다. 그래서 위상정렬을 근간으로 우선순위 큐를 사용하면 됩니다. 저는 조금 다르게 작성하기는 했지만, 기본적인 취지는 비슷합니다. 아마 지금 작성했다면, 위에 설명한대로 작성했을 것 같네요. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요... 2022. 10. 15. [C/C++] 백준 #1516 게임 개발(위상 정렬) 게임 개발 문제는 위상정렬(Topology sort)를 사용해서 풀 수 있는 문제입니다. https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 건물을 짓기 위해서 필요한 건물이 있게 되는데요. 이 필요한 건물을 위상으로 생각하면 됩니다. 건물을 짓는데 걸리는 시간이 있는데, 이것은 여러개의 입력 간선이 있다면, 그 입력 간선중 가장 긴 시간이 소요된 것으로 시간을 적으면 되죠. 기존의 위상정렬이 순서대로 나열하는 것이었다면, 여기서는 입력.. 2022. 8. 23. #79 암호 알아내기(Topology Sort) 이번문제는 난이도 5%로 아주 쉬운 문제로 분류되어 있습니다. 아마 단순무식(Brute Force) 방법으로도 풀리는 문제로 분류되어서인 듯 합니다. 숫자가 많지 않기 때문에 단순하게 조건에 맞도록 배열하는 것이 가능합니다. 예를 들어서 317 236 이 있다면, 총 숫자는 5가지 숫자가 쓰였으므로 5가지 숫자를 적절하게 배열한 다음에 조건에 맞는 수열을 고르는 것입니다. 일단 문제를 살펴본다면 다음과 같습니다. 주어진 숫자가 있습니다. 예를 들어서 531278이란 숫자가 있다면요. 이 숫자를 가지고 있음을 확인하면서, 네트웍 전송상에서 원래의 숫자를 알아내기 힘들게 하기 위해서 첫번째, 세번째, 다섯번째 숫자를 보내길 요구할 수 있습니다. 그러면 517을 전송하게 됩니다. 그런데 이러한 전송이 많아지면.. 2020. 2. 8. [C/C++] 백준 #1005 ACM Craft(위상 정렬) 그래프 이론과 관련된 알고리즘은 종류도 여러가지이고, 하나의 문제에 해법도 여러가지가 존재합니다. 프림, 다익스트라, A* 로 이루어지는 알고리즘은 같은 형태이지만, 인접 노드들을 찾아서 업데이트하는 것만 다른 알고리즘이죠. 플로이드 워샬, 크르스칼 등등 사실 다 기억하고 다닐 수도 없습니다. 이번 위상정렬 알고리즘은 간단해서 그나마 외우고 다닐만한 알고리즘이라고 생각됩니다. 문제 자체는 스타크래프트와 같은 전략시뮬레이션 게임의 테크트리와 비슷합니다. 내용이야 그렇지만, 결국 위상정렬을 통하여 최종 테크트리가 이루어지는 최단 시간을 찾는 문제입니다. 문제는 아래와 같습니다. https://www.acmicpc.net/problem/1005 위상정렬도 그래프이다보니, 인접 노드들을 인접행렬을 쓸 것인지, .. 2019. 12. 19. 이전 1 다음 728x90
