Heap4 15. 프로세스 구조(3) - Heap 1. Heap 이란? Heap은 개발자에 의해 동적으로 할당되는 메모리 영역이다. 파이썬과 같은 최신언어는 동적할당을 요구하지 않는다. 하지만, 컴퓨터의 내부 요소까지 모두 조절할 수 있는 C언어의 경우 동적할당은 필수적이다. a) 어떻게 동적할당을 할까? #include #include int main() { int *data; // 포인터 변수(주소값을 갖고 있다) data = (int *) malloc(sizeof(int)); // C언어에서 int는 32bit = 4bytes의 크기를 갖는다. // data라는 변수는 heap의 메모리 공간에 올라가게 된다. *data = 1;// 포인터 변수의 주소에(= 위치에) 1을 넣는다. printf("%d\n", *data); return 0; } mal.. 2021. 4. 14. Data Structure - 개념 정리(summary) - 이전 포스팅까지 기본적인 자료구조를 공부했습니다. 이를 기반으로, 알고리즘을 공부해 나갈 계획입니다. - 이번 포스팅은 복습 겸 앞선 포스팅에서 다뤘던 기본적인 자료구조에 대한 개념을 정리하는 포스팅입니다. 1. 자료구조와 알고리즘이란? - 자료구조(data structure): 대량의 데이터를 효율적으로 관리하기 위해 사용하는 데이터의 저장방식을 의미한다. 저장할 데이터의 특성과 데이터 사용의 목적에 따라 해당 데이터를 저장하는 방식이 달라진다. - 알고리즘(algorithm): 프로그래밍에서 어떠한 문제를 해결하거나 풀어내기 위한 방법 또는 과정을 의미한다. 수학처럼, 한가지 문제에도 다양한 알고리즘이 존재한다. 다만, 좋은 알고리즘이란 프로그래밍 상에서 가장 적은 자원(저장공간, 메모리)을 사용.. 2020. 9. 8. Data Structure - Heap(2) 1. Heap 구현 - 데이터 삭제(pop) - Heap은 최대값(max heap) 또는 최소값(min heap)만을 삭제한다. 그렇기에 root노드만을 삭제하면 된다. - root노드의 삭제는 root노드를 꺼내었을 때 발생하며, 이 동작을 pop이라고 명시한다. def pop(self): # heap에 데이터가 없는 경우 if len(self.heap_array) = len(self.heap_array): #배열의 길이보다 긴값 = 없는값 return False # 재정렬 2번 조건 - 좌측 자식노드만 존재(우측 자식노드는 없음) elif right_child >= len(self.heap_array): # 좌측 자식노드와 값을 비교하여 자식노드 값이 큰 경우 if self.heap_array[pop.. 2020. 9. 3. Data Structure - Heap(1) 1. Heap이란? - Heap은 트리구조를 기반으로한 자료구조로 데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전 이진트리(Complete Binary Tree)이다. * 완전이진트리란? → 트리에 데이터가 삽입될 때, 왼쪽에 위치한 자식노드를 먼저 채우는 규칙을 갖고 있는 이진트리이다. 이진트리이기 때문에 자식노드는 2개만 가질 수 있다. 1) Heap을 사용하는 이유 - 우선순위 큐와 같이 최대값과 최소값을 빠르게 찾기위해 사용한다. - 이를 배열로 구현하면 최대값과 최소값을 찾는데 O(n)만큼 걸린다. - 반면에, heap을 이용하여 최대값과 최소값을 찾으면 O(log n)만큼 걸린다. (더 빠르다) 2) Heap의 구조 - Heap은 최대/최소 값을 구하기 위한 구조인 최대 힙(Max H.. 2020. 8. 31. 이전 1 다음
