푸으름

✏️ 문제 링크 https://www.acmicpc.net/problem/25168 25168번: 게으른 아리를 위한 접종 계획 첫째 줄에 백신의 개수 N (1 < N ≤ 10,000)와 백신들의 선행관계 개수 M (1 ≤ M < 100,000)가 주어진다. 둘째 줄부터 M+1번째 줄까지 총 M개의 줄에 각 선행관계의 정보가 세 개의 정수 S,E (1 ≤ S < E ≤ N), 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 ✏️ 문제 설명 ✏️ 문제 풀이 기본적인 위상 정렬 문제이고 문제에서 주어진 "가능하면 쉬운 문제부터 풀어야 한다"의 조건을 주의해야 합니다. 문제의 숫자가 높아질수록 난이도가 올라가므로 우선순위 큐를 오름차순으로 정렬해서 큐를 돌려주면 됩니다. ✏️ 문제 코드 #include #include #include using namespace std; ve..

✏️ 문제 링크 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 위상 정렬로 접근해서 푸는 문제 일반적인 위상정렬로 구현하고 큐를 탐색하는 과정에서 살짝만 추가하면 문제를 해결할 수 있습니다 작업 시간 배열, 선행 관계 배열, 그리고 정답 출력 배열을 만든 후 큐를 돌리면서 ans[next] = max(ans[next], ans[node] + workTime[node])로 갱신해주시면 됩니다. 정답은 m..

Algorithm 공부 #15 - 그래프(위상 정렬) 위상 정렬(Topology Sort) ● 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 ● 항상 유일한 값으로 정렬되지 않음 ● 진입 차수 : 자기 자신을 가리키는 에지의 개수 ● 원리 파악하기 노드는 5개이고 각 노드는 1,2,3,4,5 1번 노드는 2번과 3번 노드를 / 2번 노드는 4번과 5번 노드를 / 3번 노드는 4번 노드를 4번 노드는 5번 노드를 가리키는 그래프가 있다고 가정하기 진입차수 배열 D[N] 1 2 3 4 5 0 1 1 2 2 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하기 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼주기 이 과정을 모든 노드의 ..