Heap 으로 많은 걸 할 수 있을 줄 알았는데...
개인적으로 여러 상황에 쓰일 수 있는 자료구조와 알고리즘을 공부해서 점점 확대시키면 앞으로 다가올 코테도 잘 치를 수 있을 거라고 생각했다. 근데 그런 건.... 쉽지 않은 것 같다. 자료구조를 배워도 잘 활용하는데는 경험이 좀 필요한 것 같다.
오늘은 Heap 을 공부하고 저번에 공부한 dfs 를 응용해서 완전탐색 문제를 하나 풀었다. 이번에는 오롯이 나의 힘으로 탐색 같은 기깔나는 걸 풀어서 기분이 나쁘지 않다.
Heap 기본 구현
Heap 은 기본적으로 트리의 구조를 갖는다. Heap 은 다음의 특징을 갖는다.
- Max, Min Heap 으로 나뉜다. Min Heap 은 작은 값이 우선순위를 갖기 때문에 루트 위치에 자리를 잡는다.
- Heap 은 완전 이진 트리 구조이다. 마지막 레벨을 제외하고서는 모두 채워져 있는 형태를 갖는다.
- Heap 의 큰 장점은 여러 알고리즘에 유용하게 쓰인다는 것이다.
- HeapSort
- Prim's Algorithm
- Dijkstra Algorithm
- Heap 은 배열을 사용한다. 이렇게 구현하면 편하기도 하고, 공간/시간 복잡도 측면에서 이점을 가지도록 구현할 수 있다.
| Operation | Time Complexity |
|---|---|
| remove | O(log n) |
| insert | O(log n) |
| search | O(n) |
| peek | O(n) |
기본 구현
class Heap {
typealias T = [Int]
var elements: [T] = []
var sort: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool, elements: [T] = []) {
self.sort = sort
for element in elements {
insert(element)
}
}
func leftChildIndex(from index: Int) -> Int {
(index * 2) + 1
}
func rightChildIndex(from index: Int) -> Int {
(index * 2) + 2
}
func parentIndex(from index: Int) -> Int {
(index - 1) / 2
}
// MARK: - siftUp, siftDown
func siftUp(from index: Int) {
var child = index
var parent = 0
while child > 0 && sort(elements[child], elements[parent]) {
elements.swapAt(child, parent)
child = parent
parent = parentIndex(from: child)
}
}
func siftDown(from index: Int) {
var parent = index
var candidate = 0
while true {
let lh = leftChildIndex(from: parent)
let rh = rightChildIndex(from: parent)
candidate = parent
if lh < elements.count && sort(elements[lh], elements[candidate]) {
candidate = lh
}
if rh < elements.count && sort(elements[rh], elements[candidate]) {
candidate = rh
}
if candidate == parent {
return
}
elements.swapAt(parent, candidate)
parent = candidate
}
}
func insert(_ element: T) {
elements.append(element)
siftUp(from: elements.count - 1)
}
func remove(at index: Int) -> T? {
guard index < elements.count else { return nil }
if index == elements.count - 1 {
return elements.removeLast()
}
else {
elements.swapAt(index, elements.count - 1)
defer {
siftDown(from: index)
siftUp(from: index)
}
return elements.removeLast()
}
}
func index(of element: T, start i: Int) -> Int? {
if i >= elements.count {
return nil
}
else if sort(element, elements[i]) {
return nil
}
else if element == elements[i] {
return i
}
else if let j = index(of: element, start: leftChildIndex(from: i)) {
return j
}
else if let j = index(of: element, start: rightChildIndex(from: i)) {
return j
}
return nil
}
}
extension Array: Comparable where Element == [Int] { // [Int] 를 Heap 에서 저장할 데이터로 사용할 경우.
public static func < (lhs: Array<Element>, rhs: Array<Element>) -> Bool {
if lhs[0] == rhs[0] {
return lhs[1] < rhs[1]
}
return lhs[0] < rhs[0]
}
}
Comparable
Comparable 구현에 잠시 집중해보자
extension Array: Comparable where Element == [Int] {
public static func < (lhs: Array<Element>, rhs: Array<Element>) -> Bool {
if lhs[0] == rhs[0] {
return lhs[1] < rhs[1]
}
return lhs[0] < rhs[0]
}
}이건 상당히 중요하다. 대부분 내가 구현한 Heap 에는 <, > 연산자를 생성자에 넣을 것이다. (> 이면 Min Heap, < 이면 Max Heap 이 될 것) 그리고 그렇게 사용하는 것이 코드 가독성도 좋지 않을까?
이런식으로 연산자만 사용할 수 있는 이유는 init 파라미터의 sort 가 (T, T) -> Bool 이기 때문이며, 위에 있는 < 연산자의 타입과 같다.
(T,T) -> Bool // sort
(lhs: Array<Element>, rhs: Array<Element>) -> Bool // Comparable지금은 특별히 이차원 배열인 경우 어떻게 비교할지 정의하였다. Heap 구현의 관건이 아닌가 싶다.
오늘 문제
프로그래머스 - 피로도
저녁 8시에 시작해서 새벽 2시까지 혼자 이리저리 돌려보다 겨우 풀었다..... 어휴 피곤
이 문제는 던전의 피로도 소모 정보를 가진 이차원 배열을 준다. 그리고 전체 피로도를 주는데, 피로도 소모 방식이 특이하다.
- 던전 정보인 이차원 배열의 요소는 언제나 2개이다.
- 만약 던전에 도전하고 싶을 때는 던전 정보 이차원 배열에서 하나의 던전 정보를 가져온다.
하나의 정보에서 0번 정보는 최소 피로도이다. 이 피로도만큼 남아있어야 도전이 가능한 것이다.
하지만 실제 소모되는 것은 1번 정보인 실제 피로도이다.
던전 정보를 토대로 가장 많은 던전을 도전할 수 있는 수를 구하는 프로그램을 짜는 것이다.
이거슨.... 익숙한 냄새다. 트리의 냄새가 짙게 난다.
변수의 이름을 피로도 같은걸로 할까 하다가 어차피 트리를 쓸 것이니 트리에서 자주 쓰는 변수명을 참고해서 쓰기로 하였다.
func solution(_ k:Int, _ dungeons:[[Int]]) -> Int {
var result = 0
for (index, dungeon) in dungeons.enumerated() {
var mutableDungeons = dungeons
let dTree = DTree(k: k, dungeon)
let checkDungeon = mutableDungeons.remove(at: index)
guard checkDungeon[0] <= k else { // root 노드부터 이미 방문할 수 없다면 볼 필요 없음.
continue
}
dTree.insertArray(&mutableDungeons, parent: dTree.root)
dTree.dfs(from: dTree.root, weight: dTree.root.weight, count: 1) {
if result < $0 {
result = $0
}
}
}
return result
}
class DTree {
let k: Int
var root: Node
init(k: Int, _ value: [Int]) {
self.k = k
self.root = Node(value: value[0], weight: value[1])
}
func insert(
_ insertNode: Node,
from node: Node) -> Node {
node.children.append(insertNode)
return insertNode
}
func insertArray(
_ arr: inout [[Int]],
parent: Node) {
for (index, item) in arr.enumerated() {
let newParent = insert(Node(value: item[0], weight: item[1]), from: parent)
var mutableArr = arr
mutableArr.remove(at: index)
insertArray(&mutableArr, parent: newParent)
}
}
func dfs(
from node: Node,
weight: Int, // 지금까지 사용한 피로도
count: Int, // 지금까지 방문한 던전의 수
visit: @escaping (Int)->Void) {
guard node.children.isEmpty == false else {
visit(count) // 마지막 노드까지 왔으므로 return
return
}
for i in 0..<node.children.count {
guard weight + node.children[i].value <= k else {
visit(count) // child 노드를 방문할 수 없으므로 return
continue
}
dfs(
from: node.children[i],
weight: weight + node.children[i].weight,
count: count + 1,
visit: visit)
}
}
}
class Node {
let value: Int
let weight: Int
var children: [Node] = .init()
init(value: Int, weight: Int) {
self.value = value
self.weight = weight
}
}트리는 실질적으로 데이터를 저장한다기 보단, 인터페이스를 정의하고 관리한다. 인터페이스는 insert, insertArray 두 가지로 세부적인 구현보다는 목적에 맞게 아주 간단한 구현만 하였다. 여러 guard 문을 이용해 시간효율성을 높였다.
사실 구현해보라고 해도 아무것도 참고하지 않고는 구현할 만큼의 실력은 못 된다.
이번에는 내가 승리!
바쁠것으로 생각되는 내일
내일은 우선 코테 예정된 걸 봐야 된다. 4시간에 2문제?? 점심을 먹고 커피 한잔하면서 각오를 크게 해야할 것 같다.
그와 별개로 다시 그래프에 도전해야 한다. 그래프 지나치고는 코테 마스터가 될 순 없다. 정말 정석대로 배우고 여러 방식으로 구현해야 문제를 잘 푸는데 걱정이다.
요즘은 포트폴리오 프로젝트에서 화면전환 관련 작업을 하고 있는데, 이것도 엄청 골치가 아프다. ViewModel 을 아마 새로 만들어야 할 것 같은데, 어디까지 하고 끊어야 할지가 매우 골치다.
출처
