[일반] DFS 빠삭하게 이해하기에 좋은 문제 추천
익명(skuld88)
2022-09-05 17:12
추천 0
댓글 7
다른 게시글
-
본인 지금 더닝 크루거 효과인 듯 [5][일반] 익명(122.39) | 22.09.05추천 0
-
피린이 백준 단계별 풀고있는데 [9][일반] 익명(223.38) | 22.09.05추천 0
-
요새는 설카 외모도 계속 올라가고 있음 [6][일반] 익명(skuld88) | 22.09.05추천 0
-
플랜디 개빡세네[일반] 익명(39.7) | 22.09.05추천 0
-
백준 랭킹 보면 느끼는게 [12][일반] 익명(223.39) | 22.09.05추천 1
-
골드 정수론 [5][일반] dd(175.223) | 22.09.05추천 0
-
subarray vs subsequence vs subset [3][일반] 펜져(penzer27) | 22.09.05추천 0
-
그래프에서 vertex or node 님들은 뭐씀 [12][일반] 익명(223.39) | 22.09.05추천 0
-
이거 증명해 줄 사람 [6][일반] 익명(newyearkyaru) | 22.09.05추천 0
-
언제까지 이 짓거리를 해야할까 [6][일반] 익명(106.101) | 22.09.05추천 0
그냥... 그냥 n과m 1번부터 13번까지 풀라고 그래요...
다이아인데요...
좋은 문제라고는 했지만 쉬운문제라고는 안했어요..
곧 파딱이 모동숲콘을 달 글입니다
2개씩 없엔다는거 보니 Matroid Parity Problem 생각나는데 흠 한번 풀어봄
그게 뭐임;; matroid 들어본적도 없는데 그게 정해였으면 다5보다 훨 높을듯
그냥 간단하게 이런 문제임. 그래프에서 edge 1개씩 골라낼 수 있을때 골라낸 edge들이 MST를 이루게 하려면 어떻게 해야할까? 크루스컬 알고리즘 쓰면 된다는게 잘 알려져 있지. 그런데 만약, edge의 pair들이 주어져 있고, 몇개의 pair를 골라 그 pair에 속한 모든 edge를 동시에 골라내고자 한다면, 이때 MST는 어떻게 구할까? 이게 Matroid Parity Problem이고, NP임