이분매칭
-
(라이님 블로그 대회 알고리즘 따라잡기 29)호프크로프트 카프 알고리즘(Hopcroft-Karp Algorithm)카테고리 없음 2024. 7. 24. 10:58
오늘은 호프크로프트 카프 알고리즘을 배워보았다. 블로그 글도 잘 설명되어 있지만 좋은 유튜브 영상을 하나 봐서 그것도 소개하고자 한다. 자세한 설명은 라이님 블로그 - 호프크로프트 카프 알고리즘을 참고하면 된다!!(자세한 설명에 늘 압도적 감사를 표합니더,,) 이 알고리즘의 시간복잡도는 $O(E\sqrt{V})$로 디닉 알고리즘의 특수한 경우라고 생각하면 된다. 또한 이분 매칭을 빨리 한다는 점에서 이분 매칭(Bipartite matching)과도 닮아 있는데, 디닉 알고리즘과 이분 매칭 코드를 섞어놓은 코드다. 아무래도 영문으로 된 자료가 많은 만큼 아래 유튜브에 나온 정의가 조금 더 직관적인거 같아 유튜브에 나오는 정의로 정리해본다.Hopcroft-Karp AlgorithmAugment Path) -..