베하!
문땅훈과 루피입니다.
비가 주륵주륵 내리는 금요일이네요.
날이 많이 춥다고 하니 다들 따뜻하게 입고 외출하세요!🕺
오늘은 자료구조 중 Heap에 대해서 알아보겠습니다.
개요
- 자료구조
- Heap
1. 자료구조란?
- 자료구조란 데이터 값의 모임입니다. 정의된 규칙에 의해 나열되어있고, 자료에 대한 처리를 효율적으로 수행하기 위해 자료를 구분하여 표현한 것 입니다.
- 필수 자료구조는 다음과 같습니다.
- Array(배열), Linked List(연결 리스트), Stack(스택), Queue(큐), Hash table(해시테이블), Graph(그래프), Tree(트리), Heap(힙)
오늘은 힙에 대해서 자세히 알아보겠습니다!
2. Heap
- Heap 이란?
- 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리입니다.
- 완전 이진 트리란?
- 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리입니다.
- 힙은 최대힙, 최소힙으로 나뉘어진다. 최대힙은 자식 노드보다 부모 노드의 값이 크고, 최소힙은 자식 노드보다 부모 노드의 값이 적다.
- Heap을 사용하는 이유?
- 최대값이나 최소값을 찾기위해 배열을 사용하면 O(n) 만큼 시간이 걸립니다. 하지만 힙을 사용하면 O(log n) 만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있습니다.
- 최댓값과 최솟값을 빠르게 찾아야 하는 알고리즘 등에 활용됩니다.
- O(log n)이란?
- 예를 들어, 크기가 n인 정렬된 배열에서 특정 숫자를 찾는 경우를 생각해보겠습니다. 이진 탐색을 사용하면 O(log n)의 시간 복잡도로 값을 찾을 수 있습니다.배열의 중간 값인 9와 찾고자 하는 숫자 13을 비교합니다. 9 < 13이므로 탐색 범위는 오른쪽 절반인 [11, 13, 15, 17, 19]로 좁혀집니다.마지막으로 왼쪽 절반의 배열 [11, 13]에서 중간 값인 11과 찾고자 하는 숫자 13을 비교합니다. 11 < 13이므로 탐색 범위는 오른쪽 절반인 [13]으로 좁혀집니다. 결과적으로, 이진 탐색을 통해 숫자 13을 찾는 데에는 최대 3번의 비교 연산이 필요합니다. 이는 입력 크기인 배열의 길이가 증가해도 로그 시간 복잡도인 O(log n)에 비례하는 빠른 속도로 값을 찾을 수 있다는 것을 보여줍니다. 이제 오른쪽 절반의 배열 [11, 13, 15, 17, 19]에서 중간 값인 15와 찾고자 하는 숫자 13을 비교합니다. 15 > 13이므로 탐색 범위는 왼쪽 절반인 [11, 13]로 좁혀집니다. 가령, 크기가 10인 정렬된 배열 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]에서 숫자 13을 찾는 경우를 생각해봅시다.
예시를 통해 쉽게 이해해봅시다!
- 힙의 조건
- 완전 이진 트리이다.
- 자식 노드는 부모 노드보다 작거나 같기만 하면 된다.
지금까지 힙에 대해서 알아보았습니다.
여러모로 쓰이는 알고리즘이니 익혀두시면 많이 활용될 것 같습니다!
다음에도 유익한 정보 들고 오겠습니다.
베빠!!
댓글