Hungarian algorithm (헝가리안 알고리즘, 헝가리안 메소드 / C++)
헝가리안 알고리즘 0. 주저리주저리 배정 문제(assignment problem)를 해결할 수 있는 알고리즘. 예를 들어 보면 n명의 사람이 n개의 일을 할 때, 어떤 값의 최대(or 최소) 값을 구하는 데 사용된다. 여기서 보통 어떤 값은 비용이나, 효율 등을 적용할 수 있겠다. 정말 간단하게 문제를 접근해보면, brute force의 형태로 모두 대입해 볼 수 있다. 3명이 있다고 했을 때, 사람(1,2,3)과 일(1,2,3)을 매칭 해보자. 1번 사람이 일을 맡을 수 있는 개수 3개, 2번 사람은 2개, 3번 사람은 남는 거 1개. 따라서 3! 만큼 시간이 들고, 따라서 O(n!)의 시간 복잡도를 갖게 된다. (사용불가.) 헝가리안 알고리즘(Hungarian algorithm & Hungarian ..
알고리즘/그 외
2020. 7. 8. 15:29