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만 정도 돌아야 함..
kubectl은 kubeadm init 시, master node에서 실행이 가능하다. 이 때 /etc/kubernetes/admin.conf 파일이 생성된다. 하지만 실제 kubectl은 마스터 노드 이외의 워커 노드에서도 동작할 수 있다. admin.conf 파일을 워커 노드에 복사 후, 워커 노드에서 kubectl 실행 시 정상 동작한다. 아래는 마스터 노드의 /etc/kubernetes/admin.conf를 워커 노드의 ./ 에 복사 후, kubectl 명령을 내린 결과이다. conf 파일 명시를 위해 --kubeconfig 옵션을 추가한다. vagrant@w3-k8s:~$ kubectl get nodes --kubeconfig admin.confNAME STATUS ROLES ..
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 graph에서 매칭 개수를 최대로 정하는 문제 MCMF : 각 엣지 별 비용이 있을 때, 최대 유량을 만족하는 최소 비용을 구하는 문제 할당 문제 : bipartite graph에서 매칭하고, 각 엣지 별 비용이 있을 때, 최대 매칭 시 최소 비용을 구하는 문제 (주로 1대1 대응 관계로 perfect matching 시 최소 비용을 계산) 즉, 이분 매칭은 최대 유량에서 모든 엣지의 cap이 1인 case, 할당 문제는 MCMF에서 모든 cap이 1인 case를 의미한다. (단 bipartite graph는 만족해야 함) 최대 유량 문제 계산 기법 1. Ford-Fulkerson : 최대 유량을 계산하..
이분매칭(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-..