https://www.acmicpc.net/problem/4013 주어진 그래프에서 목표 지점 중 하나까지 도달하는 경로 중 최대 cost를 얻을 수 있는 값을 구하는 문제입니다. 먼저 각 경로를 SCC로 묶으면, SCC 내에서는 해당 노드 cost 합을 얻을 수 있습니다. 그리고 SCC 간의 그래프에 대해 경로 찾기 알고리즘 등으로 최대 cost를 계산하면 됩니다. 그리고 계산된 각 scc까지의 최대 cost에 대해, 커리 가게 존재 유무를 체크하여, 최종 결과를 구하면 됩니다. 저는 edge 개수와 node 개수 최대값이 동일해, SPFA를 적용했습니다.(다익스트라도 해보니 통과하긴하지만, 아무래도 sparse한 그래프라 더 느림) 코드는 아래와 같습니다. #include #include #incl..
https://www.acmicpc.net/problem/2389 최대 100개의 점을 모두 포함하는 원의 중심과 반지름을 구하는 문제입니다. 2차원에서 원은 3개의 점으로 구할 수 있습니다. 2개의 점을 지나는 최소 원은 선분을 지름으로 하는 원입니다. (이와 같은 논리로 d차원에서는 affine independent한 d+1개의 점이 있으면, 그 점을 지나는 boundary는 유일하게 결정됩니다.)(참고 : https://freshrimpsushi.github.io/ko/posts/2385/) 100개의 점을 대상으로 100C1, 100C2, 100C3 케이스에 대해 원을 구성하고, 100개의 점들과 포함유무를 확인하는 브루트포스 방식도 가능합니다. (대충 복잡도 계산해보면 1600만 정도 돌아야 함..
https://www.acmicpc.net/problem/17412 도시 정보가 주어져 있을 때, 1번이 source, 2번이 sink인 그래프에서 최대 유량을 구하는 문제와 동일합니다. 1번에서 2번으로 가는 최대 경로 개수는 결국 모든 엣지의 cap이 1인 상황에서 최대 유량을 구하는 것과 동일합니다. 최대 유량을 구하는 기법 중 빠른 것으로 알려진 Dinic 알고리즘을 적용해보았습니다. Dinic 알고리즘에 대한 설명 및 구현은 아래 글들을 참고하였습니다. https://gazelle-and-cs.tistory.com/84 디니츠의 알고리즘 (Dinitz' Algorithm)지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다...
이분매칭(bipartite matching)은 정점들의 집합 간의 매칭을 계산하는 문제입니다. bipartite graph와 bipartite matching에 대한 설명은 아래 글을 참고하면 좋습니다.https://gazelle-and-cs.tistory.com/12 쾨니그의 정리 (Kőnig's Theorem)이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보gazelle-and-cs.tistory.com https://gazelle-and-cs.tistory.com/35 호프크로프트-카프 알고리즘 (Hopcroft-..
https://www.acmicpc.net/problem/2519 2-SAT 관련 문제입니다. 명제를 정의하는데 시간을 많이 썼지만, 실질적인 구현은 크게 어렵지 않습니다. 주어진 문제를 보면, N명의 사람들이 3개의 막대기를 갖고 있고, 각자 최대 1개의 막대기를 뺄 수 있습니다. 이 때 막대기를 뺀 상태에서 모든 막대기가 겹치는지, 겹치지 않는다면 무엇을 뺀 것인지를 구하는 문제입니다. 문제를 2-SAT 문제로 대입하면 다음과 같습니다. 2-SAT : (x1 or x2) and (x3 or x4) and .... 와 같은 CNF 에서 명제가 true가 되는 x1, x2, ... 의 해를 구할 수 있는가문제 : 모든 막대기들이 겹치지 않는가 즉, clause에 해당하는 것은 각 막대기들이 겹칠 때 ..