-
2024 조합론 및 알고리즘 여름학교아무거나적어~ 2024. 7. 23. 00:51
Day 1
- max-flow min-cut theorem
최대 흐름 문제 이해하기 (Maximum Flow Problem)
여러분이 상수도 공사의 직원이라고 해봅시다. 여러분의 업무는 물이 저장된 수원에서 물이 필요한 특정 지역까지 물을 공급하는 것입니다. 물을 공급하는 방법은 수원에서 해당 지역까지 연결
gazelle-and-cs.tistory.com
최대 흐름 최소 절단 정리 (Max-Flow Min-Cut Theorem)
저번 글에서는 최대 흐름 문제(maximum flow problem)가 무엇인지 알아 보고 최대 흐름이 만족하는 성질들도 함께 확인해 보았습니다. 최대 흐름 문제가 무엇인지 잘 모르신다면 이전 포스트를 참조하
gazelle-and-cs.tistory.com
Push Relabel Algorithm (1)
그래프의 최대 유량 (Maximum Flow) 를 찾는 문제는 웬만한 알고리즘 대회 입문서에는 다 소개되어 있는 중요한 문제이다. 일반적으로 최대 유량을 찾기 위해서는 Edmonds-Karp, Dinic과 같은 알고리즘을
koosaga.com
Day 2
쾨니그의 정리 (Kőnig's Theorem)
이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보
gazelle-and-cs.tistory.com
할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian Algorithm)
이번 포스팅에서는 assignment problem과 Hungarian algorithm에 대해서 알아보겠습니다. 먼저 assignment problem이 어떤 것인지에 대해서 살펴보고, 이를 해결하는 방법을 알아보도록 하겠습니다. 인터넷을 찾
gazelle-and-cs.tistory.com
헝가리안 알고리즘 시간 복잡도 분석
지난번에 할당 문제와 헝가리안 알고리즘을 주제로 글을 작성하였습니다. 아래 링크를 참조하세요. 2019/08/07 - [조합론적 최적화/Matching] - 할당 문제 & 헝가리안 알고리즘 (Assignment Problem & Hungarian
gazelle-and-cs.tistory.com
- tree decomposition
Day 3
- 일반매칭(blossom algorithm), Tutte-Berge minimax theorem
- tree width의 boundary를 구하는 알고리즘(gramble)
Day 4
- matroid
- grid minor theorem?
Day 5
- gomory-hu tree
- grid minor theorem 심화?
'아무거나적어~' 카테고리의 다른 글
[c++] 분수 비교할 때(__int128) 사용 (0) 2024.04.01 convex hull trick (0) 2024.04.01 Rope data structure (0) 2024.03.26 길이가 작은 segment부터 모든 subsegment을 순회하고 싶을 때 (0) 2024.03.09 dp well-known (0) 2024.03.06