jormal   2년 전

Majority number을 찾는 프로그램을 d&c를 써서 나타내야하는데... 제 머리로는 아무리생각해도 결국 전체 element를 확인해야하는거같은데... 다른방법없을까요

왼쪽절반과 오른쪽절반의 MN을 찾아서 전체를 확인해서 그게 MN임을 확인하는알고리즘 말고는 없을까요...?

pichulia   2년 전

http://www.geeksforgeeks.org/majority-element/

여기 가보시면 O(n)만에 MN을 구하는 알고리즘이 설명되어있긴 합니다...증명까진 못하겠네욬ㅋㅋ

d&c로 하면 시간복잡도가 O(n logn)이 나오는데, 이것보다 더 짧은 방법을 찾으시는건가요?

lucidash   2년 전

기본적으로 어떤 수 x 가 MN 이면 주어진 숫자들을 두 개씩 짝을 만들면 비둘기집의 원리에 따라 MN 인 녀석은 MN 인 녀석끼리 짝이 지어지거나 혼자남거나 둘 중 하나의 경우 밖에 없고 대우명제를 증명해서 O( N ) 알고리즘을 증명하면 될 것 같아요

amugeona   2년 전

잘 이해가 안되서 질문드립니다. 분할 정복으로 정렬을 수행하면 MN이 구해지는거 아닌가요?

그 외의 다른 방법을 찾으시는건가요? 

댓글을 작성하려면 로그인해야 합니다.