최대매칭 (2) 썸네일형 리스트형 텃의 정리 (Tutte's Theorem) 드넓은 황야에 위치한 초원 대학교의 컴퓨터과학과 소속 폰가젤 교수는 2인 조별 과제를 내는 것을 좋아합니다. 혼자서 해결하기에는 벅찬 문제를 두 명이서 협력하여 해결한다면 학생들에게 협동심은 물론 위기에 굴복하지 않는 능력을 기를 수 있다고 굳게 믿기 때문이죠. 물론 '조별과제 잔혹사'라는 말을 언젠간 들어 봤을 정도로 학생들의 원성이 자자하다는 사실도 잘 알고 있습니다. 그가 개설했던 알고리즘 수업의 강의 평가를 보면 쉽게 유추할 수 있었죠. 그동안은 학생들이 자율적으로 조를 편성하도록 놔두었는데, 이러니 어떤 학생들은 전혀 마음이 맞지 않는 사람과 조를 이루어야 하는 불상사가 발생했었죠. 이 부분이 바로 학생들이 가장 불편을 느낀 부분이었습니다. 이번 학기에 가젤 교수는 이러한 학생들의 원성을 잠재우.. 호프크로프트-카프 알고리즘 (Hopcroft-Karp Algorithm) 엄청 오랜만에 포스팅을 합니다. 방학이 되면 시간이 나서 글을 좀 쓸 수 있을 줄 알았는데, 대학원생은 방학도 바쁘군요. 다행히 어느정도 일단락이 나서 이렇게 글을 쓸 수 있게 되었습니다. 개강 전에 한 두 개는 더 적을 수 있지 않을까 생각합니다. 반년에 글 하나씩 올리는 주제에 블로그를 운영한다고 말할 수 있으련지는 모르겠지만, 아무튼 블로그를 운영하면서 이제 슬슬 외부에도 노출이 되어가는 것을 보니 감회가 새롭습니다. 특히 제 블로그에서 가장 조회수가 높은 글은 헝가리안 알고리즘에 관한 글이었습니다.2019/08/07 - [조합론적 최적화/Bipartite matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm) 할당 문제 &.. 이전 1 다음
