hopcroft-karp가 더 특수한 형태이고, 구현이 더 단순하기 때문입니다.
hopcroft-karp가 메모리를 더 적게 쓰고 상수가 더 작아 더 빠르게 돌긴 하지만, 시간복잡도 자체는 같기 때문에 사실상 디닉으로 풀지 못하는 문제는 없다고 보셔도 무방합니다.
세그먼트 트리와 펜윅 트리의 차이 정도라고 생각하시면 됩니다.
3736번 - System Engineer
hopcroft-karp가 더 특수한 형태이고, 구현이 더 단순하기 때문입니다.
hopcroft-karp가 메모리를 더 적게 쓰고 상수가 더 작아 더 빠르게 돌긴 하지만, 시간복잡도 자체는 같기 때문에 사실상 디닉으로 풀지 못하는 문제는 없다고 보셔도 무방합니다.
세그먼트 트리와 펜윅 트리의 차이 정도라고 생각하시면 됩니다.
댓글을 작성하려면 로그인해야 합니다.
ksjb2897 1년 전 1
hopcroft-karp 알고리즘 공부하다가 머리 깨질 것 같습니다..
제가 알기로는,
디닉 알고리즘 : 일반적인 그래프에서 가능. 시간복잡도 O(V^2E). 하지만, 이분그래프에서는 O(sqrt(V)E) 로 줄어듦.
hopcroft-karp 알고리즘 : 이분그래프에서 가능. 시간복잡도 O(sqrt(V)E)
로 알고 있습니다.
단계별로 풀어보기에서 이 문제를 마주했는데, hopcroft-karp로 풀라해서 어찌저찌 반쯤 이해한 상태로 그걸로 구현하긴 했습니다.
근데 이 알고리즘의 필요성을 모르겠습니다. 디닉 알고리즘과 시간복잡도도 같고, 디닉 알고리즘이 훨씬 쓸 수 있는 곳이 많은데(일반적인 그래프에서 가능하므로) 왜 hopcroft-karp를 배워야할까요? 이 문제는 디닉 알고리즘으로 못푸나요? 아니면, hopcroft-karp로 풀 수 있는 문제중에 디닉 알고리즘으로 못 푸는 문제가 있나요..?
도저히 이해가 안되어서 묻습니다 ㅠㅠ