CS/알고리즘2 Boyer-Moore 과반수 투표 알고리즘 Boyer-Moore 과반수 투표 알고리즘(Boyer-Moore majority vote algorithm)주어진 후보자 목록에서 과반수를 차지하는 후보를 찾는 알고리즘입니다.배열 내 과반수에 해당하는 원소가 항상 존재한다고 가정하면, 결과값은 항상 과반수 원소가 됩니다.핵심 아이디어는 주어진 후보자 목록에서 두 가지의 서로 다른 후보를 지정하고, 이들을 서로 상쇄시켜 가며 최종 후보를 결정하는 것입니다.시간 복잡도는 O(N), 공간 복잡도는 O(1) 입니다. 동작 방식 입력 시퀀스 요소 m과 카운터 c를 0으로 초기화한다.입력 시퀀스에서 각각의 요소 x에 대해서c == 0이면 m = x, c = 1 대입한다.m == x이면 c = c + 1 대입한다.m != x이면 c = c - 1 대입한다.m을 반환.. 2024. 8. 29. 알고리즘 복잡도 알고리즘 복잡도에 대해서 정리해보았습니다.알고리즘의 복잡도는 시간 복잡도와 공간 복잡도로 나뉩니다. 시간 복잡도 & 공간 복잡도최근에는 하드웨어 메모리 용량이 커졌기 때문에, 알고리즘의 성능 측정에서는 시간 복잡도가 좀 더 우선시 됩니다. 시간 복잡도시간 단위가 아닌, 알고리즘에 필요한 단계 수만을 고려합니다.데이터가 증가할수록 단계 수가 어떻게 변하는지를 말해줍니다. 공간 복잡도프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양입니다.정적으로 선언된 변수, 재귀 함수와 같이 동적으로 공간을 계속해서 필요로 하는 경우도 포함합니다. 빅 오 표기법빅 오 표기법은 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 등장했습니다.절대적인 실행 시간과 필요한 자원 공간의 양을 파악하는 것은 .. 2024. 8. 27. 이전 1 다음
