큐
간단한 두가지 구현 방법이 있는데 removeFirst()를 안쓰는 방법이 더 효율적이다.
(removeFirst()로 배열을 수정하게 되면 새로운 배열이 다시 대입되는 방식이기 때문에 오버해드 발생)
// 초간단 큐 (dequeue할 때 비효율적)
struct Queue<T> {
private var queue: [T] = []
var count: Int {
return queue.count
}
var isEmpty: Bool {
return queue.isEmpty
}
mutating func enqueue(_ element: T) {
queue.append(element)
}
mutating func dequeue() -> T? {
return isEmpty ? nil : queue.removeFirst()
}
}
// dequeue할 때 오버해드 발생 안하는 효율적인 큐
struct Queue<T> {
private var queue: [T?] = []
private var head: Int = 0
public var count: Int {
return queue.count
}
public var isEmpty: Bool {
return queue.isEmpty
}
public mutating func enqueue(_ element: T) {
queue.append(element)
}
public mutating func dequeue() -> T? {
guard head <= queue.count, let element = queue[head] else { return nil }
queue[head] = nil
head += 1
return element
}
}BFS / DFS
내가 원하는 노드 가장 빠르게 찾기 => BFS
이런저런 조건 만족하는 경로 찾기 => DFS
// BFS
func BFS(graph: [String: [String]], start: String) -> [String] {
var visitedQueue: [String] = []
var needVisitQueue: [String] = [start]
while !needVisitQueue.isEmpty {
let node: String = needVisitQueue.removeFirst()
if visitedQueue.contains(node) { continue }
visitedQueue.append(node)
needVisitQueue += graph[node] ?? []
}
return visitedQueue
}
// DFS
func DFS(graph: [String: [String]], start: String) -> [String] {
var visitedQueue: [String] = []
var needVisitStack: [String] = [start]
while !needVisitStack.isEmpty {
let node: String = needVisitStack.removeLast()
if visitedQueue.contains(node) { continue }
visitedQueue.append(node)
needVisitStack += graph[node] ?? []
}
return visitedQueue
}힙
여러 개의 값들 중 최댓값 혹은 최솟값을 효율적으로 찾아낸다.
// T는 비교 가능해야 하기 때문에 Comparable을 준수해야함
struct Heap<T: Comparable> {
var nodes: [T] = []
private let sort: (T, T) -> Bool
init(sort: @escaping (T, T) -> Bool) {
self.sort = sort
}
mutating func insert(_ data: T) {
nodes.append(data)
let lastIndex = nodes.count - 1
shiftUp(child: lastIndex)
}
mutating func remove() -> T? {
guard !nodes.isEmpty else { return nil }
nodes.swapAt(0, nodes.count - 1)
defer { shiftDown(parent: 0) }
return nodes.removeLast()
}
mutating func remove(at index: Int) -> T? {
guard index < nodes.count else { return nil }
if index == nodes.count - 1 {
return nodes.removeLast()
} else {
nodes.swapAt(index, nodes.count - 1)
defer {
shiftUp(child: index)
shiftDown(parent: index)
}
return nodes.removeLast()
}
}
public func peek() -> T? {
return nodes.first
}
// MARK: Private Methods
private func parentIndex(of child: Int) -> Int {
return (child - 1) / 2
}
private func leftChildIndex(of parent: Int) -> Int {
return (parent * 2) + 1
}
private func rightChildIndex(of parent: Int) -> Int {
return (parent * 2) + 2
}
mutating private func shiftUp(child: Int) {
var child = child
var parent = parentIndex(of: child)
// 노드의 제일 위까지 올라가거나, 부모의 노드 값과 비교했을 때 자기 자리일 때
while child > 0 && sort(nodes[child], nodes[parent]) {
nodes.swapAt(child, parent)
child = parent
parent = parentIndex(of: child)
}
}
mutating private func shiftDown(parent: Int) {
var parent = parent
while true {
let left = leftChildIndex(of: parent)
let right = rightChildIndex(of: parent)
var candidate = parent
if left < nodes.count && sort(nodes[left], nodes[candidate]) {
candidate = left
}
if right < nodes.count && sort(nodes[right], nodes[candidate]) {
candidate = right
}
if candidate == parent {
return
}
nodes.swapAt(parent, candidate)
parent = candidate
}
}
}
var heap = Heap<Int>(sort: >)
heap.insert(10)
heap.insert(100)
heap.insert(50)
heap.insert(60)
heap.insert(110)
print(heap.nodes) // [110, 100, 50, 10, 60]
heap.remove()
print(heap.nodes) // [100, 60, 50, 10]우선순위 큐
힙을 그대로 이용하여 구현하면 됩니다.
struct PriorityQueue<T> {
fileprivate var heap: Heap<T>
public init(sort: @escaping (T, T) -> Bool) {
heap = Heap(sort: sort)
}
var isEmpty: Bool {
return heap.isEmpty
}
var count: Int {
return heap.count
}
func peek() -> T? {
return heap.peek()
}
mutating func enqueue(_ element: T) {
heap.insert(element)
}
mutating func dequeue() -> T? {
return heap.remove()
}
}다익스트라 알고리즘
노드와 노드 간의 최단거리 찾기
// ex) graph - ["A": [("B",1(거리값)), ("C",3)]], start - "A"
func dijkstra(_ graph : [String: [(String,Int)]], _ start : String) -> [String:Int] {
var distances : [String:Int] = [:]
for item in graph {
distances.updateValue(Int.max, forKey: item.key)
}
// 본인 출발 도착 0
distances[start] = 0
// 우선순위 큐로 해야지 최적이지만 간단하게 배열로 구현
var pq : [(Int, String)] = [(distances[start]!, start)]
while pq.count != 0 {
pq.sort{ $0 > $1 } // 우선순위 큐로 구현 안했기 때문에 매번 정렬해줘야함
let dequeued = pq.removeLast()
let currentDistance = dequeued.0
let currentNode = dequeued.1
if distances[currentNode]! < currentDistance {
continue
}
for (adjacent,weight) in graph[currentNode]! {
let distance = currentDistance + weight
if distance < distances[adjacent]! {
distances[adjacent] = distance
pq.append((distance,adjacent))
}
}
}
return distances
}이진탐색
빠르게 탐색해보자!
func binarySearch(array: [Int], target: Int) -> Int? {
var low = 0
var high = array.count - 1
while low <= high {
let middle = (low + high) / 2
let item = array[middle]
if item == target {
return middle
} else if item > target {
high = middle - 1
} else {
low = middle + 1
}
}
return nil
}
let array = [1, 3, 4, 7, 20, 30, 31, 35, 60, 199]
print(binarySearch(array: array, target: 35)) // 7배열 탐색
순서 상관 있을 경우
func recursive(_ indexs: [Int], _ visiteIndexs: [Int]) {
print(visiteIndexs)
for index in 0..<indexs.count {
var newIndexs = indexs
newIndexs.remove(at: index)
var newVisiteIndexs = visiteIndexs
newVisiteIndexs.append(indexs[index])
recursive(newIndexs, newVisiteIndexs)
}
}
reculsive([0, 1, 2], [])
/*
[]
[0]
[0, 1]
[0, 1, 2]
[0, 2]
[0, 2, 1]
[1]
[1, 0]
[1, 0, 2]
[1, 2]
[1, 2, 0]
[2]
[2, 0]
[2, 0, 1]
[2, 1]
[2, 1, 0]
*/순서 상관 없을 경우
func recursive(_ indexs: [Int], _ visiteIndexs: [Int], _ current: Int) {
for index in current..<indexs.count {
var newVisiteIndexs = visiteIndexs
newVisiteIndexs.append(indexs[index])
print(newVisiteIndexs)
recursive(indexs, newVisiteIndexs, index + 1)
}
}
reculsive([0, 1, 2], [], 0)
/*
[0]
[0, 1]
[0, 1, 2]
[0, 2]
[1]
[1, 2]
[2]
*/
덕업일치 iOS 개발자