반응형
안녕하세요. KataRN입니다.
오랜만에 글을 쓰네요.
오늘은 우선순위 큐, 힙에 대해 알아보겠습니다.
오늘도 차례차례 알아볼게요.
1. 큐란 무엇일까요?
먼저 들어간 데이터가 먼저 나가는 데이터구조를 큐(Queue)라고 하죠.
2. 우선순위 큐란 무엇일까요?
우선순위 큐는 먼저 들어간 데이터가 먼저 나가는 것이 아닌 우선순위가 높은 순서대로 데이터가 나가는 것을 우선순위 큐(Priority Queue)라고 합니다.
3. 힙이란 무엇일까요?
힙(Heap)은 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조입니다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다. (우선순위가 최대이면 최댓값, 최소이면 최솟값입니다.)
4. 이것을 왜 알아야하나?
단순하게 알고리즘에서 최대값 최소값을 구해야하는데 비교하는 과정에서 시간초과가 나는 경우가 많습니다.
이때 사용하면 해결되기 때문에 알고있어야합니다.
5. Swift에서 제공하고있는가?
안타깝게도 Swift에서 제공하고 있지 않습니다.
파이썬은 제공하고있습니다. 저희는 구현을 해서 사용해야합니다.
우선순위 큐 코드
import Foundation
public struct Heap<T> {
private var nodes = [T]()
private var orderCriteria: (T, T) -> Bool
public init(sort: @escaping (T, T) -> Bool) {
self.orderCriteria = sort
}
public var count: Int {
return nodes.count
}
public func peek() -> T? {
return nodes.first
}
func isEmpty() -> Bool {
return nodes.isEmpty
}
public mutating func insert(_ value: T) {
nodes.append(value)
shiftUp(nodes.count - 1)
}
public mutating func remove() -> T? {
guard !nodes.isEmpty else { return nil }
if nodes.count == 1 {
return nodes.removeLast()
} else {
let value = nodes[0]
nodes[0] = nodes.removeLast()
shiftDown(0)
return value
}
}
public mutating func remove(at index: Int) -> T? {
guard index < nodes.count else { return nil }
let lastIndex = nodes.count-1
if index != lastIndex {
nodes.swapAt(index, lastIndex)
shiftDown(from: index, until: lastIndex)
shiftUp(index)
}
return nodes.removeLast()
}
private func parentIndex(ofIndex i: Int) -> Int {
return (i - 1) / 2
}
private func leftChildIndex(ofIndex i: Int) -> Int {
return 2*i + 1
}
private func rightChildIndex(ofIndex i: Int) -> Int {
return 2*i + 2
}
private mutating func shiftUp(_ index: Int) {
var childIndex = index
let child = nodes[childIndex]
var parentIndex = self.parentIndex(ofIndex: index)
while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
nodes[childIndex] = nodes[parentIndex]
childIndex = parentIndex
parentIndex = self.parentIndex(ofIndex: childIndex)
}
nodes[childIndex] = child
}
private mutating func shiftDown(from index: Int, until endIndex: Int) {
let leftChildIndex = self.leftChildIndex(ofIndex: index)
let rightChildIndex = leftChildIndex + 1
var first = index
if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
first = leftChildIndex
}
if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
first = rightChildIndex
}
if first == index { return }
nodes.swapAt(index, first)
shiftDown(from: first, until: endIndex)
}
private mutating func shiftDown(_ index: Int) {
shiftDown(from: index, until: nodes.count)
}
}
이것이 기본 큐입니다.
사용법을 간단히 설명드릴게요.
위의 코드는 큐에 대한 정의입니다. 큐에 대해 정의하고 사용하면 되죠.
var heap = Heap<Int>(sort: <)
heap.insert(3)
heap.insert(6)
heap.insert(5)
heap.insert(2)
heap.insert(4)
heap.insert(1)
//넣은 순서는 3 6 5 2 4 1 이지만 들어가면서 오름차순(sort: <)이 되어 1 2 3 4 5 6 이 된다.
//heap 변수를 선언할때 (sort: >)로 하였다면 6 5 4 3 2 1 이 되었을 것이다.
//오름차순이기 때문에 1이 나옴
heap.remove()
연습을 위해 백준의 예제문제 몇개 알려드리겠습니다.
1. 백준 1715번 카드정렬하기
https://www.acmicpc.net/problem/1715
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
2. 백준 1202번 보석도둑
https://www.acmicpc.net/problem/1202
1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
위의 문제 둘다 우선순위 힙을 이용해서 풀면 좋습니다.
풀이는 따로 적지 않겠습니다. 스포가 될 것같아서요...
저는 1715번은 어찌어찌 풀었는데 1202번은 좀 어렵네요 ㅜㅜ
더 노력하겠습니다.
오늘도 읽어주셔서 감사합니다.
- 221003 추가내용
우선순위힙을 안보고 사용하기위해 좀더 간단한 코드를 찾았습니다.
struct PriorityQueue<T> {
var heap: [T] = []
let ordered: (T, T) -> Bool
init(ordered: @escaping (T, T) -> Bool) {
self.ordered = ordered
}
/// 아래에서 위로 비교
/// 요소를 추가할때 현재 노드의 부모와 비교해서 위로 올라오는 방식을 취함
private mutating func upHeapify(_ index: Int) {
var index = index
// 힙의 index위치의 요소와 부모요소를 비교
while index > 0 && !ordered(heap[(index-1)/2], heap[index]) {
heap.swapAt((index-1)/2, index)
index = (index-1)/2
}
}
/// 위에서 아래로 비교
/// 재정렬할때 부모부터 아래로 내려가면서 검사함
private mutating func downHeapify(_ index: Int) {
var index = index
while 2 * index + 1 < heap.count {
var child = 2 * index + 1
if child < heap.count - 1 && !ordered(heap[child], heap[child+1]) {
child += 1
}
if !ordered(heap[index], heap[child]) {
heap.swapAt(index, child)
index = child
} else {
break
}
}
}
/// 큐 뒤에 요소 추가
mutating func enQueue(_ element: T) {
heap.append(element)
upHeapify(heap.count - 1)
}
/// 큐 앞요소 반환후 삭제
mutating func deQueue() -> T? {
if heap.isEmpty {
return nil
}
if heap.count == 1 {
return heap.removeFirst()
}
heap.swapAt(0, heap.count - 1)
let temp = heap.removeLast()
downHeapify(0)
return temp
}
/// front에 위치한 요소
func peek() -> T? {
return heap.first
}
var isEmpty: Bool {
heap.isEmpty
}
}
- 220308 추가내용
필요에 따라 아래처럼 이용가능합니다.
감사합니다.
import Foundation
public struct Heap<T> {
private var nodes = [T]()
private var orderCriteria: (T, T) -> Bool
public init(sort: @escaping (T, T) -> Bool) {
self.orderCriteria = sort
}
public init(array: [T], sort: @escaping (T, T) -> Bool) {
self.orderCriteria = sort
configureHeap(from: array)
}
public var count: Int {
return nodes.count
}
public func peek() -> T? {
return nodes.first
}
func isEmpty() -> Bool {
return nodes.isEmpty
}
public mutating func insert(_ value: T) {
nodes.append(value)
shiftUp(nodes.count - 1)
}
public mutating func remove() -> T? {
guard !nodes.isEmpty else { return nil }
if nodes.count == 1 {
return nodes.removeLast()
} else {
let value = nodes[0]
nodes[0] = nodes.removeLast()
shiftDown(0)
return value
}
}
public mutating func remove(at index: Int) -> T? {
guard index < nodes.count else { return nil }
let lastIndex = nodes.count-1
if index != lastIndex {
nodes.swapAt(index, lastIndex)
shiftDown(from: index, until: lastIndex)
shiftUp(index)
}
return nodes.removeLast()
}
private mutating func configureHeap(from array: [T]) {
nodes = array
for i in stride(from: nodes.count/2 - 1, through: 0, by: -1) {
shiftDown(i)
}
}
private func parentIndex(ofIndex i: Int) -> Int {
return (i - 1) / 2
}
private func leftChildIndex(ofIndex i: Int) -> Int {
return 2*i + 1
}
private func rightChildIndex(ofIndex i: Int) -> Int {
return 2*i + 2
}
private mutating func shiftUp(_ index: Int) {
var childIndex = index
let child = nodes[childIndex] // 처음에 노드를 저장해두고 인덱스를 구한 후 바꿔준다.
var parentIndex = self.parentIndex(ofIndex: index)
while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
nodes[childIndex] = nodes[parentIndex]
childIndex = parentIndex
parentIndex = self.parentIndex(ofIndex: childIndex)
}
nodes[childIndex] = child
}
private mutating func shiftDown(from index: Int, until endIndex: Int) {
let leftChildIndex = self.leftChildIndex(ofIndex: index)
let rightChildIndex = leftChildIndex + 1
var first = index
if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
first = leftChildIndex
}
if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
first = rightChildIndex
}
if first == index { return }
nodes.swapAt(index, first)
shiftDown(from: first, until: endIndex)
}
private mutating func shiftDown(_ index: Int) {
shiftDown(from: index, until: nodes.count)
}
}
var heap = Heap<(Int, Int)>(array: [], sort: { $0.0 < $1.0 })
반응형
'Old_SWIFT(221012) > 알고리즘이야기' 카테고리의 다른 글
| 백준 시간초과 해결방법 (0) | 2022.02.28 |
|---|---|
| 백준에서 코딩테스트 해보기 (0) | 2022.02.20 |
| 최단거리 구하기 <다익스트라(Dijkstra)>, <플로이드 워셜(Floyd Warshall)> (0) | 2021.12.08 |
| DP(동적계획법) (0) | 2021.11.16 |
| DFS, BFS에 대해 알아봅시다. (0) | 2021.11.15 |