이분매칭 관련 문제에서 질문있습니다.

  • infoefficiency
    infoefficiency

    책 1034p 에서 이분매칭으로 최대 독립집합을 찾을 때

    적절한 자료구조를 사용하면 코드를 최적화 할 수 있다고 하였는데

    어떠한 방법을 사용하여아 하는지 힌트좀 주실수 있을까요?

    감사합니다 ^^


    10년 전
1개의 댓글이 있습니다.
  • restart
    restart

    아마 그래프 표현을 인접행렬이 아니라 인접리스트 표현으로 바꾸는 걸 말하는 게 아닐까요? 격자그래프이므로 한 정점에 연결된 간선은 최대 4개이므로 인접행렬은 낭비죠. 인접리스트의 경우 시간복잡도는 O(VE)->O(V²)가 되지 싶습니다. 물론 진짜 의도는 종만님만이..


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.