공부공간

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 작업의 우선순위 중, 최소시간을 구하기 위해서 위상정렬을 통하여 차수에 대한 누적합을 구해줍니다. 정렬이 끝난 후, Sum의 값중 가장 큰 값이 정답입니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import j..

www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제집에서 순서가 존재하기때문에 차수를 고려한 위상정렬을 진행해준다. 다만, 문제 번호가 1-N 까지 문제중에서 차수가 0 이되었을때에 우선순위를 부여해야한다 ( 쉬운문제 부터 푼다 ) 따라서, 우선순위큐에 문제번호가 낮은 차수가 0 인 노드부터 처리해주자 import java.io.BufferedReader; import java.io.InputStreamReader; impor..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부� www.acmicpc.net 위상정렬과 다이나믹프로그래밍(약간?)이 결합된 문제이다. 빌드와 시간이라는 개념이 등장하여 1 ->2 ->3 , 11->10->3 의 노드 연결정보에서 3의 진입차수가 0 이될때 1->2 / 11->10의 비용중 큰것을 골라야지 다른 빌드에서 걸리는 시간을 커버하면서 진행 할 수 있다. 중간중간 첫 건물이 목표건물인 경우와같이 예외사항을 처리해주면서 진행하면 풀리는 문제.. 위상정렬을 DF..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 가수의 수가 나오고, 그 뒤로는 그 가수들의 순서가 나온다. N은 1이상 1,000이하의 정수이고, M은 1이상 100이하의 정수이다. www.acmicpc.net 음악프로그램에 N명의 참가자가 일부 순서가 정해져있을때에 서로다른 M가지의 일부순서를 만족하는 하나의 전체순서를 구하는 전형적인 위상정렬문제이다. 만약 그래프에 사이클이 생겼을때에는 전체 N을 방문하지 않고 끝나므로, Indegree배열에 0이..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 위상 정렬 ( Topology Sort )는 그래프의 진입 차수를 기준으로 다음 올 그래프의 순서를 정하는 정렬알고리즘이다. 먼저 위상 정렬의 순서는 다음과 같다. 1. 그래프에서 진입차수가 0인 노드들을 큐에 넣는다. 2. 큐에서 하나씩 poll 하면서, 그 노드와 연결된 그래프들의 진입차수를 -1해준다 ( 큐에서 poll ..