MathTrauma

제공되는 priority queue 를 사용하는 대신 Min Heap 을 직접 구현해서 최단 경로 문제를 풀어보았다. 문제 링크 : https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net pos 배열은 정점의 번호를 heap 내부의 위치로 바꾸어 준다. x=pos[id]; 이 코드는 id 정점이 heap 의 x 위치에 해당된다는 뜻이다. pos 에 대해 일종의 역함수인 rev 배열은 heap 의 위치에 대응되는 정점의..

문제 링크 : 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 ..

문제 링크 : https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 지원 비용의 크기가 크지 않아서 각 node(공항) 를 방문했을 때, 다른 비용으로 도달했으면 다른 node 처럼 생각하고 최단 경로를 찾으면 된다. '시간'과 '비용' 두 가지 값을 다루기 때문에 헷갈릴 수 있으니 변수명을 정리하자. 다익스트라 알고리즘을 사용하는데 이중 배열 Dst의 값은 시간이다. 즉, '시간'='거리' 로 처리한다. 거리(..

문제 링크 : https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 배열 arr[i] 은 i=1 부터 시작하고, 구간[i-1, i] 에 세워진 기둥의 높이로 간주했다. 넓이가 최대가 되는 직사각형의 밑변이 구간 [L, R] 이라고 가정해 보자. 이 구간에서 arr[i]의 값이 최소가 되는 것을 찾아야 한다. ( $ L arr[j] 를 만족하는 j 를 찾으면 ml[i] 가 된다. 이 때, 다음의..