Heap
완전이진트리로서 부모노드가 자식노드보다 크거나 작은 순서로 정렬되어있는 자료구조를 말합니다. 부모노드가 자식노드보다 작으면 최소힙이라고 부르고, 크면 최대힙이라고 부릅니다.
여기서 완전이진트리란 트리의 왼쪽부터 봤을 때 노드가 비어있지 않은 구조를 말합니다.
힙은 배열로 표현이 가능한데 루트노드를 1인 인덱스로 가정합니다. 루트노드를 중심으로 왼쪽 자식노드는 2 * 부모인덱스, 오른쪽 자식노드는 (2 * 부모인덱스) + 1 가 됩니다.
힙의 삽입 및 삭제에 대해서 알아보겠습니다.
최소힙을 기준으로 알아보겠습니다. 맨 위 루트 노드는 모든 노드중 가장 작은 노드가 될 것입니다.
- 삽입
이 트리에 어떠한 값을 append합니다. 그리고 부모노드와 비교해 가면서 자신의 자리를 찾아갑니다.
- 삭제
삭제는 무조건 루트 삭제하게 됩니다. 최소힙의 경우 가장 작은 값이 먼저 나오게 될 것입니다.
이를 코드로 구현할 때 순서는 다음과 같습니다.
1. 리프노드와 루트노드를 교환합니다.
2. 루트노드(기존 리프노드)를 자식노드들과 비교하면서 제자리를 찾아갑니다.
힙에 관련된 문제를 풀 때 생각하면서 까다로웠던 점은 최대힙구현이었습니다. 파이썬은 최소힙을 기준으로 실행되고 이를 최대힙으로 바꾸기 위해서는 튜플형태로 만들거나 음수로 바꿔서 추출할 때 다시 '-'를 붙여서 빼오는 방법이 있습니다.
정렬
정렬에는 여러가지 알고리즘이 있습니다. 순서대로 차근차근 복습해보겠습니다.
1. Bubble Sort
맨 앞 두 수를 비교하여 큰 값을 뒤로 차근차근 보내는 알고리즘 입니다.
n(n - 1) / 2 이므로 O(N^2)의 시간 복잡도를 가집니다.
2. Selection Sort
리스트 중 가장 작은 값을 찾아서 현재 인덱스와 값을 바꾸는 알고리즘입니다.
역시 버블정렬과 마찬가지로 n(n - 1) / 2 이므로 O(N^2)의 시간 복잡도를 가집니다.
3. Insertion Sort
정렬된 부분과 정렬되지 않은 두 부분으로 나눠서 정렬되지 않은 값을 정렬된 리스트에 맞는 인덱스에 넣는 알고리즘입니다.
오름차순으로 정렬할 때 최악의 경우는 내림차순으로 정렬되어있는 리스트이며 시간복잡도는 O(N^2)입니다.
4. Quick Sort
맨 뒤 값을 pivot으로 설정하고 맨앞부터 시작하여 pivot보다 작은 경우 그대로 두고 pivot보다 크면 자리를 교환합니다.
끝나면 pivot보다 작은값과 큰값으로 나눠지게 되는데 pivot을 그 사이에 위치합니다. 이 과정을 반복함으로써 정렬할 수 있습니다.
pivot이 중간값과 근사하지 않을 경우 최악의 경우인 O(N^2)의 시간복잡도를 가집니다.
5. Merge Sort
배열을 반으로 쪼개지지 않을 때까지 쪼갠 후 이를 다시 붙일 때 정렬하여 완성하는 알고리즘입니다. 쪼갤 때는 1/2로 나뉘기 때문에 높이는 logN이며 각 단계에서 N만큼 비교하기 때문에 총시간복잡도는 O(NlogN) 이 됩니다.
6. Heap Sort
파이썬에서 보통 heapq라는 라이브러리를 이용하며 최소힙이 디폴트로 실행됩니다. 힙에 넣음과 동시에 자동으로 정렬되며 데이터를 뽑을 때는 무조건 루트노드, 즉 최소값부터 나오게 됩니다.
삽입과 추출은 제일 위에서 힙에서 설명드렸던 방식대로 움직이게 됩니다.
시간복잡도는 O(NlogN) 을 가집니다.
'부트캠프' 카테고리의 다른 글
[WIL] Middleware, N+1 문제 정리 및 해결 (0) | 2022.04.25 |
---|---|
[26일차] TIL - Dynamic Programming (0) | 2022.04.06 |
[23일차] TIL 이진 탐색(Binary Search) - (1) (0) | 2022.04.01 |
[22일차] TIL - Week3 Test (0) | 2022.03.31 |
[19일차] TIL (Quick Sort) (0) | 2022.03.28 |