구사과

POI 1996. Canoes 먼저 각각의 사람을 몸무게 순으로 정렬해 놓읍시다. 가장 가벼운 사람은 다른 사람과 보트를 태워 보내는 것이 합리적으로 보이니, 가장 가벼운 사람을 보낼 때는, 다른 사람 한 명을 잡아서 같이 보트를 태워 보냅니다. 같이 탈 수 있는 사람이 여럿이면 물론 몸무게가 무거운 사람을 보내는 것이 현명합니다. 두 번째, 세 번째로 가벼운 사람들에게 이를 반복하고, 같이 태워 보낼 수 있는 사람이 없을 때까지 이를 반복합니다. 이 알고리즘의 구현은, 정렬된 배열에서 현재 보낼 무거운 사람의 “포인터” 를 가지고 있으면 간편합니다. 가벼운 사람이 있을 때, 이 사람의 몸무게를 맞출 수 있을 때까지 포인터를 앞으로 (몸무게가 감소되는 쪽으로) 내려주고, 그 사람과 매칭시킨 후, 포인터를..

(Lecture note is essentially an English version of this post. Slides are used for presentation.) 원 논문 (arxiv) 그래프의 최소 컷 (Minimum cut) 은 그래프를 연결되지 않게 하기 위해서 지워야 하는 간선 가중치의 최소 합이다. 가중치가 없는 경우에, 최소 컷은 그래프의 connectivity 를 정의하는 수량이 된다. 고로 최소 컷은 그래프가 주어졌을 때 계산하고 싶은 가장 기초적인 수량에 해당되며, 응용 예시 또한 무수히 많다. 그래프의 최소 컷을 계산하는 방법은 크게 3가지가 있다. 아래에 해당 방법의 발견 시간 순으로 나열한다. (아래 요약은 이 논문에서 따왔다.) Min-cut Max-flow 접근. Gl..

작년 가을에 버추얼 후기 느낌으로 적어놓고, 올리려고 하다가 여러 이유로 포스팅하지 않았던 글. 거의 1년동안 하드에서 잠자고 있던 텍스트다! 포스팅을 미룬 이유는 여러가지가 있다. 당연히 제일 큰 이유는 귀찮고 관심 없었기 때문이지만, 나름대로 통신교육 자료로 사용하려는 목적도 있었고, 업솔빙을 적당히 하고 보완해서 올리려는 목적도 있었다. 통신교육에는 이미 충분히 우려먹은 것 같아 별 상관이 없어 보이고, 업솔빙은 끝이 없을 것 같아서 그냥 올린다. 여담으로 여기 언급된 문제중 2019 가을 통신교육에 총 9문제가 사용되었다. 알아서 잘 찾아보자. Day 5/6/8에 대해서는 Part 2에 적을 예정이다 (이건 적어 놓은 게 없다. 아주 먼 미래에 올라올 듯 :p) Day 3/4/7에 대해서는 딱히 ..