24.06.23 알고리즘

알고리즘

힙 정렬(Heap Sort)

• 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다.
• 불안정 정렬에 속한다.

완전 이진 트리

• 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조이다.
• 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 한다.

과정

1. 최대 힙을 구성한다.
2. 현재 힙 루트는 가장 큰 값이 존재한다. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나를 줄인다.
3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다.

유용한 경우

• 가장 크거나 가장 작은 값을 구할 때
• 최대 k만큼 떨어진 요소들을 정렬할

이분 탐색(Binary Search)

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식

과정

• 우선 정렬을 해야한다.
• left와 right로 mid 값을 설정한다.
• mid와 내가 구하고자 하는 값과 비교한다
• 구할 값이 mid보다 높으면 left = mid + 1, 구할 값이 mid보다 낮으면 right = mid - 1 로 설정한다
• left > right가 될 때까지 반복한다.