path_cover (1) 썸네일형 리스트형 최소 경로 덮개 (Minimum Path Cover) 얼마 전 친한 형님이 또 재미있는 문제를 하나 소개해주었습니다. 처음에 전 그 문제가 NP-난해일 것이라고 생각했지만, 토의를 거친 끝에 그 문제가 순환이 없는 방향 그래프(directed acyclic graph, DAG)에서 최소 경로 덮개(minimum path cover)를 찾는 문제로 환원될 수 있다는 것을 찾아냈습니다. 또한 놀랍게도, 일반적인 그래프에서 최소 경로 덮개를 찾는 문제는 NP-난해하지만, DAG에서는 다항 시간에 찾을 수 있다는 것도 알게 되었습니다. Bipartite matching을 활용하면 된다는데, 곰곰이 생각해 보니 쉽게 보일 수 있더군요. 이번 포스트에서는 이에 대해서 간단히 알아보도록 하겠습니다. 문제를 엄밀히 정의하도록 하겠습니다. 입력으로는 방향이 있는 그래프(d.. 이전 1 다음
