구사과

(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에 대해서는 딱히 ..

(2020/06/13 6월 과제가 완성되어서 공개했습니다.) (2020/04/18 초판 작성.) 이미 아시는 분들도 계시겠지만, 2017년 가을 이후 포스팅되는 대부분의 글은 삼성전자 SW멤버십의 지원을 받아 작성되고 있습니다. 매달 컴퓨터 과학에 관한 글을 주기적으로 SW멤버십에 제공하고, 이에 따른 지원금을 받는 식입니다. 비정기적으로 관리하던 블로그에 매달 주기적으로 글이 올라올 수 있게 된 것은 SW멤버십의 지원 덕분이 큽니다. 감사합니다. SW멤버십에 제공하는 대다수의 글은 제 블로그에 같이 올립니다. 일반적으로 제출 기한이 있는 SW멤버십에 글을 먼저 제출한 후, 데드라인 안에 손보지 못한 부분이 있으면 이 부분을 보강해서 블로그에 올리는 식입니다. 잘못된 사실이나 오탈자 등도 블로그 글 우선..