📌 Peak Finder
One Dimensional
Straightforward Algorithm
- 순차 탐색 O(N)
순차적으로 탐색하여 이전과 이후의 값이 더 크면 peak이다.하지만 O(n)이기 때문에 효율적인 방법은 아니다. - 효율적인 방법 O(lgN)
Step 1. 중간 지점 탐색
Step 2. 중간 지점의 좌우 index를 비교하여 중간값보다 작은 곳은 모두 생략
Step 3. Step1, 2를 반복하다가 좌우 모두 중간값보다 작으면 중간값이 peak📌 Sorting
📍 Insertion Sort
Time Complexity : O(N²)
Step 1. 모든 원소를 순차적으로 탐색
Step 2. 탐색한 원소를 앞의 배열의 원소들과 비교하며 자신의 위치를 찾아서 삽입
Step 3. 마지막 원소를 탐색하면서 정렬된 배열 반환📍 Merge Sort
Time Complexity : O(NlgN)
Step 1. N = 1 일 때까지 배열 분열
Step 2. 다시 합병하면서 정렬
Step 3. 마지막 합병을 하면서 정렬된 배열 반환📍 Counting Sort
Time Complexity : O(N) (제한된 입력값에 한하여 사용)
Condition
Array의 각 원소는 1~10 이내의 값을 가진 원소이다.
Search Sequence
Step 1. 1 ~ 10의 index를 가지는 배열을 초기화
Step 2. 배열을 탐색하면서 탐색된 원소가 e일 때 array[e]++📍 Heap Sort
Feature
힙 정렬은 삽입과 동시에 정렬이 효율적으로 이루어져야 한다. 이러한 성질 때문에 PriorityQueue에서 정렬 알고리즘으로 사용한다.
- Tree 구조Tree가 배열의 형태로 존재하며 index를 통해 부모와 자식을 구별한다.
Max Heap
- Max HeapifyHeapify하는 원소의 자식들과 본인을 비교한다. 자신이 최대가 아니면 최대값 자식과 값을 바꾸며 바뀐 방향으로 재귀적 heapify를 수행한다.
- 정렬root부터 max heapify를 수행한다.
- 삽입배열의 마지막에 삽입하며 부모와 비교하면서 자신이 더 크면 부모와 교환하고 재귀적으로 비교한다.
Hello, Devs!