궁금한게 많은 개발자 노트

우선순위 큐를 사용하여 가장 큰 두 돌을 꺼내 같으면 둘 다 제거하고, 차이가 있다면 큰 돌의 무게에서 작은 돌의 무게를 빼서 다시 큐에 넣어 마지막 남은 돌의 무게를 반환하는 문제입니다. 만약 모두 제거되었다면 0을 반환합니다. #define swap(a,b,t)((t) = (a), (a) = (b), (b) = (t)) class Solution { public: int heap[31] = {0,}; int heap_size = 0; void insert_heap(int item) { heap[++heap_size] = item; int current = heap_size; int temp; while (current /2 >= 1 && heap[current] > heap[current/2]) { ..

시험장에서 자주 사용하는 Heap에 대해 적어보려한다. Heap이란, 최솟값이나 최댓값을 빠르게 찾아 내기 위해 고안된 완전이진트리의 일종으로 우선순위큐라고도 불린다. (적다보니 트리에 대해서도 적어봐야지 싶다) Heap에는 최대힙(Max Heap), 최소힙(Min Heap)이 있는데 부모 자식노드 관계에 따라 정해진다. 예를들어, A가 B의 부모 노드라면, A의 key값과 B의 key값은 대소관계가 성립한다 (Max는 부모가 key값이 크다) -> key(T.parent(v)) key(v) 일반적으로 정렬을 해야할 상황이 생기면 Heap에 모두 넣고, 하나씩 빼면 정렬된 형태로 값을 얻을 수 있어서 자주 사용하며 시간복잡도는 O(logN)으로 Qu..