구사과

https://en.wikipedia.org/wiki/Karger's_algorithm 그래프에서의 Minimum Cut은 그래프의 컴포넌트를 2개로 쪼개는 데 삭제해야 하는 간선의 개수를 뜻한다. (가중치를 붙여서 일반화한 경우도 있다. 지금 소개하는 알고리즘은 그 경우는 해결하지 못하는 걸로 알고 있음)이 중 정점 S와 T의 Minimum Cut을 구하는 것은 (즉, S와 T를 서로 다른 컴포넌트로 쪼개는 데 필요한 간선수) 알고리즘이 알려져 있다. (http://amugelab.tistory.com/entry/%EC%9C%A0%EB%9F%89-%EA%B4%80%EB%A0%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC) Minimum Cut의..

http://www.koistudy.net/?mid=prob_page&NO=2058 재밌는 문제.. 텔레포터를 타고 여기저기 옮겨나간다는 문제의 개념이 상당히 당황스러울 가능성이 높다. 막히지 않으려면 "그래프"라는 사실을 빠르게 파악해야 한다. 나뉘어진 선분 구간은 정점이고. 텔레포트는 간선이라는 것을 관찰하면 * 경로 간선의 개수를 최대화 * indegree와 outdegree는 모두 1이다 (시작 끝점 빼고) * 텔레포터의 설치는 두 정점 i, j의 나가는 간선의 교환이다 이 사실을 파악하면 문제가 상당히 깔끔해진다. 먼저 그래프의 성질을 관찰하자. * 컴포넌트 내의 indeg / outdeg가 모두 1이면 컴포넌트는 사이클을 이룬다. * 고로 그래프는 사이클 컴포넌트들의 집합이다.. 근데 시작 끝..

https://www.acmicpc.net/problem/3323 일전에 한번 멘붕이라고 언급한 적이 있었는데 (http://amugelab.tistory.com/entry/201573-2015723-problem-solving) 제대로 접근하면 아주 어렵지는 않다. 먼저 삼각형 쿼리를 뜯어보자. 한 점이 원점인 삼각형이면, 각도 범위 안에 있는 점들 중에서, 해당 선분 아래에 있는 점이 존재하는가? 를 묻는 문제가 됨을 알 수 있다.그러면 각도 범위를 무력화하면 어떨까..? 그러면 꽤 유명한 문제다. (https://www.acmicpc.net/problem/7057) 들어오는 점 집합을 Convex Hull만 남겨두고, 이진 탐색을 하면 풀 수 있다. 복잡한 설명은 생략.. 문제는 쿼리가 구간으로 들..