MathTrauma

문제 링크 : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리를 구하는 데에는 대표적인 두 알고리즘인 Prim 알고리즘과 Kruskal 알고리즘이 있다. 두 가지 모두 구현하고 몇 가지 첨언한다. 1. Kruskal Algorithm 간선의 가중치를 오름차순으로 정렬하여 하나씩 조사한다. 기존에 선택된 간선들과 cycle 을 형성하지 않으면 선택한다. cycle 을 확인하는 방법으로..

문제 링크 : https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 입력을 문자열 str 로 받아서 처리한다. p 를 문자열에서 현재 처리할 index 라 하자. dp[p] 는 p 를 시작 위치로 하는 부분 문제의 결과값을 의미한다. 세 가지 가능성이 있다. 1. 더 이상 진행이 불가능한 경우 -> str[p] 가 '0' 이 경우 해당 수를 알파벳에 대응시킬 방법이 없다. 더 이상 진행하지 않고 return 0 을 하면 된다. 가짓수를 세는 문제니 0 을 돌려준다는 ..

문제 링크 : https://www.acmicpc.net/problem/11377 11377번: 열혈강호 3 첫째 줄에 직원의 수 N과 일의 개수 M, 일을 2개할 수 있는 직원의 수 K가 주어진다. (1 ≤ N, M ≤ 1,000, 1 ≤ K ≤ N) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있 www.acmicpc.net Max-Flow 관련해서 머리 속에서 raw flow 와 net flow 이 뒤섞여서 헤맸던 과거를 떠올리며... 할 일도 없는데 Push Relabel Algorithm 을 공부해 두자. Max-Flow Min-Cut 정리의 한줄 요약 중간 과정에서 어떤 방식으로 flow를 흘려도 max flow에 도달하지 못한 상황에서는 augment ..