https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 문제를 읽어보면 위상정렬 알고리즘임을 알 수 있다. 위상정렬 알고리즘: https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.c..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 위상정렬문제인데 입력값이 이전의 문제와 다르게 들어온다. **중복된 간선이 들어올 수 있기 때문에 주의해야한다. : 집합으로 해결해주었습니다. 코드 # 2623번 음악프로그램 import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) graph = [set() for _ in ..

https://www.acmicpc.net/status?group_id=13709 채점 현황 www.acmicpc.net 풀이 건물을 짓기 위해서는 선행으로 지어져야하는 건물이 존재한다. - 위상정렬 알고리즘을 적용해야함을 알 수 있다. 위상정렬 알고리즘: https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com 코드 # 1516번 게임개발 import sys from collections import deque n = int(sys.stdin.r..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 문제를 읽고나서 위상정렬 알고리즘임을 어렵지않게 알 수 있었다. 최소 건설 시간을 측정하기 위해 다이내믹 프로그래밍을 사용할 것이다. 건물 완성까지의 최소 시간을 구하기 위해서는 다음과 같은 말이 성립된다. - 선행 건설 되어야하는 건물이 존재한다면 후행 건설을 실시 할 수 없다. - 이를 위해서는 선행 건설 되어야하는 건물이 모두 건설되어야 한다는 얘기이다. - 선행 건설이 없는 건물..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 조건을 다시 정리하자면 1) 문제 번호는 낮을수록 쉬운 문제이다. 최대한 쉬운 문제를 먼저 풀면서 모든 문제를 풀어야한다. 2) 최대한 쉬운 문제를 먼저 푼다는 얘기는 문제번호가 내림차순으로 풀어야하는 조건이 주어질 수 있다는 얘기이다. - 진입차수가 존재하는 노드가 있다는 얘기이다. 3) 진출차수와 진입차수가 존재하지않는 노드와 진출차수는 존재하지만 진입차수가..

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 풀이 위상정렬 알고리즘은 다음과 같다. https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com..