본 글은 딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』
강의를 듣고 정리한 내용입니다.
강의와 수업 자료에 수록된 일부 코드와 이미지를 참고하여 발췌·활용하였습니다.
코딩테스트 준비를 체계적으로 하고 싶으시다면, 아래 링크에서 강의를 확인해 보세요
👉 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 보러 가기
본 게시물은 파트너스 활동의 일환으로 작성되었으며, 구매 시 소정의 수수료를 받을 수 있습니다.
힙
힙이란?
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 이다.
또한 힙은 특정 순서에 맞춰서 항상 데이터를 정렬해두는 자료구조이기 때문에 데이를 뽑아올 때 항상 순서대로 값을 가져올 수 있다.
정렬이랑 다른 점
정렬은 항상 O(NlogN) 만큼의 시간 복잡도가 걸리는 연산이다. 힙이라는 자료구조는, 데이터를 가져오고 빼는 데 O(logN) 만큼의 시간 복잡도가 걸리는 대신 매번 정렬을 해주지 않아도 정렬된 상태를 유지할 수 있다.
그래서 정렬된 데이터 삽입 삭제가 잦은 상황에서는 힙을 쓰는 것이 더 효율적이다.
힙의 구현
힙은 항상 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있도록 하는 자료구조이다. 다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 한다.
예를 들면 아래와 같다.
8 Level 0
6 3 Level 1
2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 5 Level 2 # 자식 노드보다 크지 않아서 힙이 아닙니다..!
힙의 종류
- Max Heap : 최댓값이 맨 위인 힙
- Min Heap : 최솟값이 맨 위인 힙
Max Heap 원소 추가
원소를 추가할 때는 다음과 같이 하면 된다.
- 원소를 맨 마지막에 넣는다.
- 부모 노드와 비교 후 , 더 크다면 자리를 바꾼다.
- 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2 과정을 반복한다.
이 맥스 힙에서 9를 추가해보겠습니다!
8 Level 0
6 3 Level 1
4 2 1 Level 2
1. 맨 마지막에 원소를 넣습니다.
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다.
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
코드로 구현
위 과정을 코드로 구현해보자.
- 전체 배열에 값을 추가한다.
- cur_index 를 len(self.items) -1 부터 시작한다.
- 맨 뒤에 인덱스부터 시작하기 위해
- 맨 뒤 인덱스부터 부모 노드의 인덱스의 노드와 값을 비교한다.
- 만약 값이 더 크다면 값을 교체하고
- cur_index 에 parent_index 를 넣는다.
- 이 과정은 cur_index 가 제일 꼭대기 칸인 1 이 되기 전까지 반복하면 된다.
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
self.items.append(value)
cur_index = len(self.items) - 1
while cur_index > 1:
parent_index = cur_index // 2
if self.items[parent_index] < self.items[cur_index]:
self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
cur_index = parent_index
else:
break
max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items) # [None, 8, 6, 7, 2, 5, 4]시간 복잡도
insert() 를 하면 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올린다.
완전 이진트리의 최대 높이는 O(logN) 이였다. 그러면 반복하는 최대 횟수도 O(logN) 이 된다.
즉, 맥스 힙의 원소 추가는 O(logN) 만큼의 시간 복잡도를 가진다고 분석할 수 있다.
Max heap 원소 제거
맥스 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.
스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없다. 또한 원소를 추가했던 것과 마찬가지로 원소를 삭제할때도 힙의 규칙이 지켜져야 한다.
원소 제거 구현
- 루트 노드와 맨 끝에 있는 원소를 교체한다.
- 맨 뒤에 있는 원소를 삭제한다.
- 변경된 노드와 자식 노드들을 비교한다.
- 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.
- 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달할 때까지 3 과정을 반복한다.
- 2 에서 제거한 원래 루트 노드를 반환한다.
이 맥스 힙에서 원소를 제거해보겠습니다! (항상 맨 위의 루트 노드가 제거 됩니다.)
8 Level 0
6 7 Level 1
2 5 4 3 Level 2
1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
8 Level 0
6 7 Level 1
2 5 4 3 Level 2
3 Level 0
6 7 Level 1
2 5 4 8 Level 2
2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제합니다.
이 값이 기존 맥스힙에 있던 가장 큰 값입니다. 따라서 이 값을 마지막에는 반환해줘야 합니다!
3 Level 0
6 7 Level 1
2 5 4 X Level 2
3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 합니다.
우선 부모와 왼쪽 자식을 비교합니다. 그리고 부모와 오른쪽 자식을 비교합니다.
그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경해야 합니다.
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경합니다.
3 Level 0
6 7 Level 1
2 5 4 Level 2
7 Level 0
6 3 Level 1
2 5 4 Level 2
3-2. 다시 자식 노드와 비교합니다.
우선 부모와 왼쪽 자식을 비교합니다.
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경합니다.
7 Level 0
6 3 Level 1
2 5 4 Level 2
7 Level 0
6 4 Level 1
2 5 3 Level 2
4. 가장 아래 레벨에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삭제했습니다!
7 Level 0
6 4 Level 1
2 5 3 Level 2
5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환하면 됩니다!
코드로 구현
위에서 생각했던 방법을 그대로 코드로 구현하면 된다.
- 0번째 원소는 None 이 들어가 있으니 1번째와 len(self.items) -1 번째를 바꾸면 된다.
- 맨 뒤의 원소를 뽑아 prev_max 변수에 저장한다.
- 루트 원소의 인덱스인 1부터 비교를 시작한다.
- max_index 라는 변수에 현재 인덱스를 저장한다.
- 왼쪽 자신의 값과 비교한다.
- 이 때, 자식의 인덱스가 배열의 사이즈보다 크지 않은지 확인해줘야 한다.
- 만약 왼쪽 자식이 더 크다면 max_index 에 left_child_index 를 넣는다.
- 그리고 오른쪽 자식의 값과 비교한다.
- 만약 오른쪽 자식이 더 크다면 max_index 에 right_child_index 를 넣는다.
- max_index 가 현재 인덱스와 같으면
- 부모 노드가 두 자식 보다 크다는 의미이다.
- 더 교체하지 않아도 된다는 의미이므로 반복문을 끝낸다.
- 아까 저장해놨던 prev_max 를 반환하면 된다.
...
def delete(self):
self.items[1], self.items[-1] = self.items[-1], self.items[1]
prev_max = self.items.pop()
cur_index = 1
while cur_index <= len(self.items) - 1:
left_child_index = cur_index * 2
right_child_index = cur_index * 2 + 1
max_index = cur_index
if left_child_index <= len(self.items) - 1 and self.items[left_child_index] > self.items[max_index]:
max_index = left_child_index
if right_child_index <= len(self.items) - 1 and self.items[right_child_index] > self.items[max_index]:
max_index = right_child_index
if max_index == cur_index:
break
self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
cur_index = max_index
return prev_max
...
'인프런 > 딩코딩코 알고리즘' 카테고리의 다른 글
| [딩코딩코 2025 코딩테스트 필수 알고리즘] - 18. DFS & BFS (0) | 2025.11.10 |
|---|---|
| [딩코딩코 2025 코딩테스트 필수 알고리즘] - 17. 그래프 (0) | 2025.11.10 |
| [딩코딩코 2025 코딩테스트 필수 알고리즘] - 15.트리 (0) | 2025.11.02 |
| [딩코딩코 2025 코딩테스트 필수 알고리즘] - 14.해쉬 (0) | 2025.10.31 |
| [딩코딩코 2025 코딩테스트 필수 알고리즘] - 13. 큐 (0) | 2025.09.11 |