카테고리 없음
2020-07-24 06시 개발자 글 모음 | "Weighted Min-Cut: Se" 외 2개 이야기
데브피드
2020. 7. 24. 06:46
- 이번 포스팅에서는 같은 회사에 다니고 있는 동기인 개발자2(Gary)와 약 1년여간 진행했던 토이프로젝트에 대해서 회고해보려고 합니다
- 저희가 1년 동안 토이프로젝트로 개발한 무브(Moobe)는 Map of Youtube의 약어이자 Move(움직이다) 와의 비슷한 발음을 통해 '유튜버들이 다녀온 곳으로 이동하다'라는 느낌을 줄 수 있는 중의적 의미를 내포하고 있습니다
- 저희는 협업을 위한 툴로 Git을 사용하였고 개발하기전 모든 기능 개발에 대한 Issue를 발행하고 각자가 맡은 기능들은 해당 feature에 개발한 후 검토하고 Merge하는 방식으로 진행하였습니다
- 2-respecting min cut을 $O(m \log n + n \log^4 n)$ 시간에 찾는 알고리즘에 대한 논문이 소개되었다
- 스패닝 트리 $T$ 가 주어졌을 때 $T$ 의 간선과의 교집합이 1개 이하인 최소 컷인 1-respecting min-cut 을 모두 $O(n)$ 번의 호출로 찾았다고 생각하고 넘어가자
- 이렇게 할 경우 $O(\log^2 n)$ 개의 cut-query로 $e_j$ 를 찾을 수 있다