본문 바로가기

IT/Algorithm16

Boyer–Moore Majority Vote 우연찮게 본 Boyer-Moore majority vote 알고리즘에 대해 알아보려고 한다. Boyer-Moore는 사람 이름이라 제외하고 Majority vote만 보면, 말 그대로 가반수 값을 찾는 알고리즘이다.때문에 단순히 input 데이터 중 반복되는 값이 많은 것을 찾는 것이다. 그림 1. Boyer-Moore Majority Vote 그림 1을 보면 좀더 확실하게 알 수 있다. X축 밑에 그림이 각 순차적인 인덱스 별로 나오는 값이고 Y축 값은 Majority 값의 개수를 나타낸다.그래서 맨 처음 0으로 시작하다 마지막엔 빨간색 네모가 카운트 4까지 위치하는 것을 볼 수 있다. 결과적으로 빨간색 네모가 해당 input 데이터 중 가반수를 차지한다는 의미이다. 이처럼 가반수의 값이 무엇인지 쉽게.. 2019. 6. 6.
Insertion Sort Insertion Sort는 이름에서 드러나듯 값을 어딘가(?)에 넣어서 정렬한다. 글로는 어려 울 수 있으니 간단히 Flow를 확인하면 다음과 같다.12, 11, 13, 5, 6Let us loop for i = 1 (second element of the array) to 4 (last element of the array)i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12 11, 12, 13, 5, 6i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13 11, 12, 13, 5, 6i = 3. 5 will move to the b.. 2019. 6. 6.
Selection Sort Selection Sort는 이름 상에서도 알 수 있듯이 무언가(?)를 선택해서 정렬하는 방식이다. arr[] = 64 25 12 22 11 // Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64 // Find the minimum element in ar.. 2019. 6. 6.
HeapSort HeapSort에 대해 알아보려고 한다. HeapSort는 Binary Heap 자료 구조를 기반으로 Selection Sort와 거의 비슷하다. 잠깐, 본격적으로 알아보기 전에 Binary Heap에 대해 먼저 알아보자.Binary Heap은 완전한 Binary Tree (마지막 노드를 제외하고 각 Level에 노드가 가득찬 것 - 거의 완전하게 노드로 가득찬 Tree)이다. 그림 1. Complete Binary Tree 위의 그림처럼 구성되는데 일반 Binary Tree와는 다르게 Binary Heap은 부모 노드를 2가지 방식으로 채운다. 하나는 두 자식 노드 보다 값이 클 때이고 다른 하나는 두 자식 노드 보다 값이 작을 때이다. (각각 max heap, min heap)이처럼 Heap Sort.. 2019. 6. 5.

티스토리툴바