heap (4) 썸네일형 리스트형 [BOJ] 백준 11286 절댓값 힙 (Swift) 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최소 힙과 최대 힙 2개를 사용해서 풀이할 수 있는 문제입니다. x가 양수라면 최소 힙에 넣어주고, x가 음수라면 최대 힙에 넣어줍시다. 그렇다면 최소 힙과 최대 힙에 절대값이 작은 수가 루트 노드에 위치할 것입니다. pop을 해줄 때, 최소 힙과 최대 힙이 둘다 비어있다면, 0을 출력하고 최소 힙만 비어있다면 최대 힙에서 pop, 최대 힙만 비어있다면 최소 힙에서.. [BOJ] 백준 1927 최소 힙 (Swift) 문제 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 문제 그대로 최소 힙을 사용해 풀이할 수 있는 문제입니다. Swift에서는 힙 자료구조를 지원하지 않기 때문에 직접 구현해주어야 합니다. 참고용으로 힙을 구현한 포스팅을 올려놓았습니다. https://dev-mandos.tistory.com/244 [자료구조] Heap에 대해 알아보고 구현해보기 (Swift) Heap이란? Heap은 트리를 사용하고, 트리 중 에서도.. [BOJ] 백준 11279 최대 힙 (Swift) 문제 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 문제 그대로 최대 힙을 사용해 풀이할 수 있는 문제입니다. Swift에서는 힙 자료구조를 지원하지 않기 때문에 직접 구현해주어야 합니다. 최대 힙을 구현하기만 하면 되는 문제.. 입니다. 참고용으로 힙을 구현한 포스팅을 올려놓았습니다. https://dev-mandos.tistory.com/244 [자료구조] Heap에 대해 알아보고 구현해보기 (Swift) He.. [자료구조] Heap에 대해 알아보고 구현해보기 (Swift) Heap이란? Heap은 트리를 사용하고, 트리 중 에서도 완전이진트리를 기본으로 한 자료구조입니다. 주로 최솟값과 최댓값을 빠르게 찾기 위해서 사용하는데, 루트노드를 최댓값으로 사용하면 최대힙이되고, 최소값으로 사용하면 최소힙이 됩니다. 시간 복잡도 삽입 : $O(log_n)$ 삭제 : $O(log_n)$ 구현 array를 사용하여 구현하고, 값을 비교하기 위해 Comparable 프로토콜을 채택한 자료형에 대해서만 요소로 사용할 수 있도록 구현하였습니다. 삽입 완전 이진 트리의 마지막 요소에 삽입 (append 사용) 삽입된 요소를 부모노드와 비교 최대힙이라면, 부모노드보다 더 크다면 swap 최소힙이라면, 부모노드보다 더 작다면 swap 루트노드가 될 때 까지 반복 삭제 힙의 루트 노드와 마지막 노.. 이전 1 다음
