그냥 하는 노트와 메모장

BOJ 9522 - 직선 게임[ 분류 : 이분 매칭(Bipartite matching), Greedy, Game theory ] 문제가 다소 독특하여 포스팅하고자 한다. 나는 증가경로를 이용하여 접근해봤다. 문제를 보면 알겠지만, 한 점에 대해 x축 또는 y축에 그을 수 있으므로, 총 2개의 직선을 그을 수 있다. 그렇다면 처음에 게임을 시작하는 상근이는 시작할 점과 축을 정하고, 그 이후에 여기에 종속되어 번갈아 가며 이전 직선 위의 점을 선택해야 한다. 즉, 상근이는 점뿐만 아니라 축도 정할 수 있다. 축이 정해진 시점에서 x축과 y축이 번갈아가며 등장하는 구조가 될 수밖에 없다(1). 또 x와 y에 대해 이분 그래프를 구성할 수 있다. x축에 평행하는 서로 다른 두 개의 직선은 절대로 겹칠 수 없고..

[Network flow, MCMF] Graph modeling practices 네트워크 플로우 및 MCMF에서는 그래프 모델링이 큰 비중을 차지합니다. 모델링을 하고나서 플로우 흘리는 개념은 고정되어 있으나, 그 문제가 그래프인지 또 그래프임을 알더라도 모델링을 하지 못하면 풀기 못하는 경우가 허다합니다. 이 게시물은 그래프 모델링에 있어, 신기하거나 재밌게 느꼈던 문제 및 제가 어떻게 그래프 모델링 했는지 소개하고자 합니다. 물론! 다른 풀이가 있을 수 있으니 참고바래요 :) ※ 이분 그래프에 대한 내용은 포함되지 않았습니다. 호프 크로프트 또는 이분 매칭 문제를 찾으시는 분은 다른 게시물을 찾아보시길 바래요. ※ 소스코드는 일부러 첨부하지 않았습니다. 제 소스가 궁금하신 분들은 댓글 남겨주시면 쪽..