프로그래밍/알고리즘1 [알고리즘] Moore's voting algorithm leetcode의 169. Majority Element 문제를 풀다가 알게된 알고리즘입니다. 이 알고리즘은 처음 들어봐서 공부하고 정리했습니다. 1. 배경문제를 간단하게 요약하면,array 에 (array의 length // 2) 번 넘게 나타나는 원소를 찾는 것입니다. 처음에는 sort를 이용하려고 했는데, O(nlogn) 시간복잡도가 생기고 공간은 O(1) 를 사용하게 됩니다.하지만 문제 맨 마지막 줄에 선형 시간 + 공간 O(1) 만 사용해서 풀 수 있다는 글이 있었습니다. 도저히 모르겠어서 결국 해답을 봤고, Moore's voting 알고리즘을 알게 되었습니다. 2. 알고리즘 이 알고리즘은 stream algorithim 입니다.(데이터 스트림을 처리하는 알고리즘) 배열에 중복되는 데이터.. 2025. 3. 27. 이전 1 다음