구사과

당시 대회에서 실제로 맞닥뜨린 문제인데, O(NlgN) 풀이에 꽤 근접했지만 (ㅠㅠ) 결국 제대로 된 풀이를 만드는 데 실패하고 O(N^2lgN) 의 풀이를 짤 수밖에 없었다. 문제는 상당히 단순하다. 이것저것 description이 복잡하게 들어와 있지만 요약하자면 K = 1인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 |Ai - X| + |Bi - X| 를 최소화 하는 X를 찾으면,K = 2인 경우 N개의 (Ai,Bi) 쌍이 주어졌을 때 min(|Ai - X| + |Bi - X|,|Ai - Y| + |Bi - Y|) 를 최소화하는 X,Y를 찾으면 된다. K = 1인 경우는 쉬운 그리디 알고리즘이 존재한다. 2N개의 원소가 들어있는 A + B 집합에서의 N번째 원소가 답이다. 복잡도는 O(NlgN) ..

https://www.acmicpc.net/problem/9495 혼자 못풀고 결국 풀이를 봤는데, 풀이가 상당히 멋져서 소개. 득점을 하는 방법을 쭉 따져보자.1. 절대 'x'로 득점을 할 수 없다.2. 'o'로 득점을 하려면 주위에 있는 '.' 들은 모두 차있어야 한다. 즉 주위에 있는 '_'에서 득점할 수 없다.3. '_'로 득점을 하려면 주위에 있는 'o' 들은 모두 차있어야 한다. 즉 주위에 있는 'o' 에서 득점할 수 없다. 벌써 답이 나왔다. 인접한 'o' - '.' 쌍을 모두 이었을 때의 최대 독립 집합 정점 수 를 계산하면 이 문제를 풀 수 있다. degree가 0인 'o'는 없음이 문제 조건에 있으며, '.'는 그냥 넣어줘도 무방하다.새롭게 생기는 그래프는 일단 격자 그래프의 subgr..

https://www.acmicpc.net/problem/1210 1. 최소 코스트 구하기 문제를 뒤집어서 에지를 막을 때 일정한 코스트가 든다고 가정한다면, 이 문제는 Minimum Cut이라는 유명한 문제로 바뀐다는 것을 알 수 있다. Minimum Cut은 Maximum Flow와 동치임이 잘 알려져 있으므로 이러한 문제는 쉽게 풀 수 있다. (http://koistudy.net/?mid=prob_page&NO=1236)다만, 애석하게도 이 문제에서는 정점을 막을 것을 요구하고 있기 때문에 이것만으로는 안 풀린다. 하지만 약간의 변형을 거치면 이 역시 Minimum Cut을 사용해서 쉽게 풀 수 있다. 정점을 In(i), Out(i)라는 두 정점으로 분할하자. In(i)는 이 정점으로 들어오는 간선..