고코딩

문제 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다. 출력 입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 ..

항상 문제를 풀때마다 힙(heap)에 대한 개념이 많이 헷갈려서 포스팅한다. 다른 분의 블로그에 매우 잘 정리된 포스팅을 가져와 정리해서 쓴 글이다. 힙(Heap) 힙은 이진트리의 일종이다. 반정렬 상태(정렬된 상태가 아니다)이며, 완전이진트리와는 다르게 중복값이 허용된다. 삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다. 보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이다. 힙은 최대힙, 최소힙으로 나뉘어진다. 최대힙은 부모노드가 자식노드보다 큼 이라는 특징을 가지고 최소힙은 부모노드가 자식노드보다 작음 이라는 특징을 가지고 있다. 이러한 특징으로 힙에 값을 넣게 되면 최소힙에서는 최소값 순으로, 최대힙에서는 최대값 순으로 값을 얻을수 있다. 힙 자료구조는 보통 ..