힙
-
백준 1715 카드 정렬하기Algorithm/BOJ 2021. 4. 7. 12:57
출처: www.acmicpc.net/problem/1715 분류: 우선순위 큐, 힙 접근방식 가장 최소인 값 두 개를 계속 더해가면 되는 문제입니다. 문제는 어떻게 최소 두 개를 찾을지가 관건이네요. 역시 최대, 최소 하면 제일 먼저 떠오르는 건 힙이겠죠? 힙으로 풀어봤습니다. Heap 에 대해 궁금하시다면 여기로 다른 분들 풀이를 보니 이분탐색으로 풀어도 아슬아슬하게 통과는 되는 것 같더라구요. 해결방법 public struct Heap { private var nodes = [T]() private var orderCriteria: (T, T) -> Bool public init(sort: @escaping (T, T) -> Bool) { // 최대 힙인지 최소 힙인지 기준을 잡는다. self.ord..
-
백준 1927, 11279 최소 최대 힙Algorithm/BOJ 2021. 1. 11. 10:49
출처: https://www.acmicpc.net/problem/1927 , https://www.acmicpc.net/problem/11279 분류: 자료구조, 힙 접근방식 최대 or 최소를 최상위에 두는 heap 을 사용하는 문제였습니다. 복습하는 느낌으로 필요한 부분만 직접 구현해봤습니다 :) 해결방법 heap 을 생성할 때 기준을 정해줘서 최대, 최소 힙을 만들 수 있습니다. heap(by: Bool init(by criteria: @escaping (T, T) -> Bool) { self.criteria = criteria } mutating func insert(_ value: T) { nodes.append(value) shiftUp(from: nodes.count-1) } mutating ..
-
HeapComputer Science/DataStructure 2019. 12. 31. 20:32
Heap 이란? 힙은 루트에 가장 힙한 녀석을 두는 이진 트리이다. (응?) 루트에 항상 최대 또는 최소값을 두기 때문에 최대 최소값을 빠르게 얻을 수 있다. O(1) 힙은 완전 이진트리의 모습을 띄는데, 부모 노드가 자식 노드보다 크거나(최대힙) 작은지(최소힙) 만을 보장한다. 즉, 자식노드 끼리는 큰지 작은지를 비교할 수가 없다. 힙은 배열로 구현하면 공간, 시간 복잡도 측면에서 좋기 때문에 배열로 많이 구현한다. 배열로 구현했을 때 다음과 같이 인덱스를 구할 수 있다. parent: floor((i-1) / 2) left: 2i + 1 right: 2i + 2 인덱스를 1부터 시작하면 parent: i/2, left: 2i, right: 2i+1 로 구할 수도 있다. 잘 보면 오른쪽 노드 = 왼쪽노..