14.데이터 구조 (siwft)
1. Bubble Sort
var a = [2,6,3,1]
print(a.count)
func bubbleSort(_ array: inout [Int]) {
// 스캔 작업 반복
for index1 in 0 ..< (array.count - 1) { // 0~2
var isSwap = false
// 스캔 작업(인접 인덱스 비교 및 swap 반복) : (탐색하려는 요소의 갯수) - 1
// => 탐색하려는 요소의 갯수는 스캔 횟수에 따라 차감됨(스캔 횟수만큼 정렬되어 있을테니)
for index2 in 0 ..< ( (array.count - index1) - 1 ) {
// 앞에숫자가 크다면
if array[index2] > array[index2 + 1] {
//교환
array.swapAt(index2, (index2 + 1))
//교환 했다는것 표시
isSwap = true
}
}
// 교환이 끝나면 종료
if isSwap == false { return }
}
}
bubbleSort(&a)
// 함수 내부의 파라미터는 기본적으로 상수(let) 이기 때문에 inout 으로 선언해야 바꿀수 있다
2. Select sort
var array = [4,6,1,3]
func select(_ array : inout [Int] ) {
for i in 0 ..< (array.count - 1) {
var min = i
for i2 in (i + 1) ..< array.count {
if array[min] > array[i2] {
min = i2
}
}
array.swapAt(i, min)
}
}
select(&array)
3. Insertion Sort
var array = [9,8,1,2]
func i (_ arr:inout[Int]){
for i in 1..<arr.count{
for i2 in stride(from: i, to: 0, by: -1){
if arr[i2] < arr[i2-1]{
arr.swapAt(i2, i2-1)
} else {
break
}
}
}
}
i(&array)
func insert(_ array : inout [ Int ]) {
for stand in 1 ..< array.count {
for index in stride(from : stand , to : 0 , by: -1) {
if array[index] < array[index - 1] {
array.swapAt(index, index - 1 )
} else {
break
}
}
}
}
insert(&array)
// 선택 < 버블 < 삽입 정렬 순으로 빠르나 거의 비슷비슷하게 느림
4. 재귀
// 일반 factorial 구현 ( 2! = 1x2 , 3! = 1x2x3 )
// for 루프가 1번있기 때문에 시간복잡도 O(n)
// result 변수 1개, 루프 상수 n 1개 로 2개의 공간복잡도 O(1)
func f(_ num : Int) -> Int {
var result = 1
for n in 2...num {
result *= n
}
return result
}
// 재귀 factorial 구현
// 반복문을 n-1번 호출하기때문에 O(n-1)이지만 상수는 날리기때문에 O(n)
// 입력 n에 따라 (n-1) 변수가 생성되기 때문에 공간복잡도 O(n)
func rf(_ num : Int) -> Int {
if num <= 1 {
return num
} // 탈출 조건이 없는 경우 무한 재귀에 빠질수 있다
return (num * rf(num - 1))
}
f(3)
rf(3)
5. Dynamic programming
func fibo(_ n : Int) -> Int {
var cache : [Int] = [0,1]
for num in 2...n {
cache.append(cache[num - 1] + cache[num - 2])
}
return cache[n]
}
fibo(4)
// 재귀를 이용한 구현
func rfibo(_ n: Int) -> Int {
if n <= 1 {return n}
return rfibo(n - 1) + rfibo(n - 2)
}
rfibo(4)
// 재귀에선 0,1,2,3 번째 값까지 구한뒤 저장하고 이걸 이용해서 2,3 index의 값을
// 활용하는 것이기 때문에 실행속도가 재귀에 비하여 빠르다
// 동적 계획법, 분할 계획법 공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분할하여 문제를 해결
// 동적 계획법 차이점 : - 작은 단위로 쪼개진 문제들은 상위 문제를 해결하는 데 재사용 됨
// - Memoization 기법을 사용함
// 분할 계획법 차이점 : - 작은 단위로 쪼개진 문제들은 상위 문제를 해결하는 데 재사용되지 않음
// - Memorization 기법을 사용 안함
6. Quick Sort
var array = [7,10,3,9,1]
func quickSort(_ array: [Int]) -> [Int] {
guard let first = array.first, array.count > 1 else {
return array
}
let pivot = first
let left = array.filter { $0 < pivot }
let right = array.filter { $0 > pivot }
return quickSort(left) + [pivot] + quickSort(right)
}
quickSort(array)
7. Merge Sort
var array = [6,5,3,1,8,7,2,4]
func mergeSort(_ array : [Int]) -> [Int] {
if array.count <= 1 { return array }
let center = array.count / 2
let left = Array(array[0..<center])
let right = Array(array[center..<array.count])
func merge(_ left:[Int], _ right:[Int]) -> [Int] {
var left = left
var right = right
var result : [Int] = []
while !left.isEmpty && !right.isEmpty {
if left[0] < right[0] {
result.append(left.removeFirst())
} else {
result.append(right.removeFirst())
}
}
if !left.isEmpty {
result.append(contentsOf:left)
}
if !right.isEmpty {
result.append(contentsOf:right)
}
return result
}
return merge(mergeSort(left), mergeSort(right))
}
mergeSort(array)
8. 완전 탐색
func sequencial(_ array: [Int], num: Int) -> Bool {
for element in array {
if num == element {
return true
}
}
return false
}
9. Binary search
// 재귀 함수로 구현하기
func binarySearch(_ array: [Int], num: Int) -> Bool {
if array.count == 1 {
return array[0] == num ? true : false
}
let mid = array.count / 2
let range = array[mid] > num ? (0..<mid) : ((mid + 1)..<array.count)
return binarySearch(Array(array[range]), num: num)
}
// 반복문으로 구현하기
func binarySearch2(_ array: [Int], num: Int) -> Bool {
var start = 0
var end = (array.count - 1)
while start <= end {
let mid = (start + end) / 2
if array[mid] == num { return true }
if array[mid] > num {
end = mid - 1
} else {
start = mid + 1
}
}
return false
}
10. Graph - BFS
//BFS 너비우선탐색
// 같은 레벨의 노드를 우선탐색한다
//너비 우선 탐색은 보통 두 개의 큐(Queue)로 구현
//방문 해야하는 노드를 저장하는 Queue(이하,needVisitStack)
//이미 방문한 노드를 저장하는 Stack(이하, visitedQueue)
// 1 탐색할 노드의 데이터를 needVisitQueue에 넣는다
// 2 needVisitQueue의 첫 번째 값을 추출해서(FIFO), visitedQueue에 해당 값이 존재하는지 확인한다 ( visitedQueue에 존재하지 않는 값이 나올 때까지 반복 )
// 3 추출된 값이 visitedQueue에 존재하지 않으면, visitedQueue에 추가한다
let graph: [String: [String]] = [
"A" : ["B", "C"],
"B" : ["A", "D", "E"],
"C" : ["A", "F"],
"D" : ["B"],
"E" : ["B"],
"F" : ["C"],
]
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
}
BFS(graph: graph,start: "A")
11. DFS
// DFS
// 방문 해야하는 노드를 저장하는 stack(needVisitStack)
// 이미 방문한 노드를 저장하는 Queue(visitedQueue)
// 1 탐색할 노드의 데이터를 needVisitStack에 넣는다
// 2 추출된 값이 visitedQueue에 존재하지 않으면 visitedQueue에 추가한다
// 3 추출된 값에 연결된 간선들을 모두 needVisitStack에 추가한다
let graph: [String: [String]] = [
"A" : ["B", "C"],
"B" : ["A", "D", "E"],
"C" : ["A", "F"],
"D" : ["B"],
"E" : ["B"],
"F" : ["C"],
]
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
}
DFS(graph: graph, start :"A")
12. Heap
// Heap
// 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 "완전 이진 트리"
// 최대 힙의 Root Node는 항상 최대 값
// 부모 노드의 인덱스 번호 = 자식 노드의 인덱스 번호 / 2
// 왼쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * 2
// 오른쪽 자식 노드의 인덱스 번호 = (부모 노드 인덱스 번호 * 2) + 1
//
//struct Heap<T: Comparable> {
// var heap: Array<T> = []
//
// init() { }
// init(data: T) {
// heap.append(data) // 0번 index 채우기용
// heap.append(data) // 실제 Root Node 채우기
// }
//}
//
//
//// insert(_:) : 데이터 삽입하기
//// ① 완전 이진 트리 구조에 맞춰 일단 삽입한다(데이터 비교 X)
//// ② 삽입된 데이터의 크기가 부모노드의 데이터보다 작을 때까지 swap 해준다 (반복 작업)
//
//mutating func insert(_ data: T) {
// if heap.count == 0 {
// heap.append(data)
// heap.append(data)
// return
// }
//
// heap.append(data)
//
// func isMoveUp(_ insertIndex: Int) -> Bool {
// if insertIndex <= 1 { // 루트 노드일 때
// return false
// }
// let parentIndex: Int = insertIndex / 2
// return heap[insertIndex] > heap[parentIndex] ? true : false
// }
//
// var insertIndex: Int = heap.count - 1
// while isMoveUp(insertIndex) {
// let parentIndex: Int = insertIndex / 2
// heap.swapAt(insertIndex, parentIndex)
// insertIndex = parentIndex
// }
//}
//
//
//var heap = Heap.init(50)
//heap.insert(100)
//heap.insert(30)
//heap.insert(10)
//
//
//
//// pop() : 데이터 꺼내기(삭제하기)
//// ① 가장 큰 값인 Root Node를 삭제한다(Return 값)
//// ② 가장 마지막에 추가된 노드(배열 마지막 요소)를 Root Node로 이동한다
//// ③ 이동된 Root Node의 데이터가 왼쪽, 오른쪽 자식 노드의 데이터보다 클 때까지,자식 노드 중 큰 값을 가진 노드와 swap 해준다 (반복 작업)
//
//enum moveDownStatus { case none, left, right }
//
//mutating func pop() -> T? {
// if heap.count <= 1 { return nil }
//
// let returnData = heap[1]
// heap.swapAt(1, heap.count - 1)
// heap.removeLast()
//
// func moveDown(_ poppedIndex: Int) -> moveDownStatus {
// let leftChildIndex = (poppedIndex * 2)
// let rightChildIndex = leftChildIndex + 1
//
// // case 1. 모든(왼쪽) 자식 노드가 없는 경우 (완전이진트리는 왼쪽부터 채워지므로)
// if leftChildIndex >= heap.count {
// return .none
// }
//
// // case 2. 왼쪽 자식 노드만 있는 경우
// if rightChildIndex >= heap.count {
// return heap[leftChildIndex] > heap[poppedIndex] ? .left : .none
// }
//
// // case 3. 왼쪽 & 오른쪽 자식 노드 모두 있는 경우
// // case 3-1. 자식들이 자신보다 모두 작은 경우
// if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightChildIndex] < heap[poppedIndex]) {
// return .none
// }
//
// // case 3-2. 자식들이 자신보다 모두 큰 경우 (왼쪽과 오른쪽 자식 중 더 큰 자식 선별)
// if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightChildIndex] > heap[poppedIndex]) {
// return heap[leftChildIndex] > heap[rightChildIndex] ? .left : .right
// }
//
// // case 3-3. 왼쪽 & 오른쪽 중 한 자식만 자신보다 큰 경우
// return heap[leftChildIndex] > heap[poppedIndex] ? .left : .right
// }
//
// var poppedIndex = 1
// while true {
// switch moveDown(poppedIndex) {
// case .none:
// return returnData
// case .left:
// let leftChildIndex = poppedIndex * 2
// heap.swapAt(poppedIndex, leftChildIndex)
// poppedIndex = leftChildIndex
// case .right:
// let rightChildIndex = (poppedIndex * 2) + 1
// heap.swapAt(poppedIndex, rightChildIndex)
// poppedIndex = rightChildIndex
//
// }
// }
//}
//
//
//
//var heap = Heap.init(30)
//heap.insert(20)
//heap.insert(18)
//heap.insert(9)
//heap.insert(6)
//heap.insert(50)
//
//print(heap)
//print("pop data == \(heap.pop()!)")
//print(heap)
//
//
//
//
//
struct Heap2<T> {
var nodes: [T] = []
let comparer: (T,T) -> Bool
var isEmpty: Bool {
return nodes.isEmpty
}
init(comparer: @escaping (T,T) -> Bool) {
self.comparer = comparer
}
func peek() -> T? {
return nodes.first
}
mutating func insert(_ element: T) {
var index = nodes.count
nodes.append(element) // 만약 현재 트리가 포화 상태라면, 새로운 레벨에 노드를 넣고, 포화 상태가 아니라면 현재 레벨에 노드를 붙인다.
while index > 0, !comparer(nodes[index],nodes[(index-1)/2]) {
nodes.swapAt(index, (index-1)/2)
index = (index-1)/2
} // 부모 노드가 있을 경우, 부모노드와의 대소관계 규칙을 만족하는 지 확인합니다. 만족하지 못하는 경우, 부모 노드와 자식 노드를 교환한 뒤, 부모노드로 이동한 뒤 이 과정을 반복합니다. 만족하는 경우는 삽입 과정을 종료합니다.
}
mutating func delete() -> T? {
guard !nodes.isEmpty else {
return nil
}
if nodes.count == 1 {
return nodes.removeFirst()
}
let result = nodes.first
nodes.swapAt(0, nodes.count-1) // 힙의 루트 노드와 힙의 마지막 레벨의 가장 오른쪽 노드를 맞바꿉니다.
nodes.popLast() // 힙의 마지막 레벨의 가장 오른쪽 노드(원래의 루트노드)를 제거합니다.
var index = 0
while index < nodes.count {
// 루트노드에서 시작해서 자식 노드와 대소 관계를 비교합니다. 이때 자식이 둘일 경우는 부모 노드와 바꿨을 때 자식 노드와 대소관계 규칙을 유지할 수 있도록 바꿔줍니다.
let left = index * 2 + 1
let right = left + 1
if right < nodes.count {
// 오른쪽 노드가 존재하는 경우
if comparer(nodes[left], nodes[right]),
!comparer(nodes[right], nodes[index]) {
nodes.swapAt(right, index)
index = right
} else if !comparer(nodes[left], nodes[index]){
nodes.swapAt(left, index)
index = left
} else {
break
}
} else if left < nodes.count {
// 왼쪽 노드만 존재하는 경우
if !comparer(nodes[left], nodes[index]) {
nodes.swapAt(left, index)
index = left
} else {
break
}
} else {
break
}
}
return result
}
}
var heap: Heap2<Int> = Heap2 { $0 < $1 } // Max Heap 생성
heap.insert(20)
heap.insert(30)
heap.insert(18)
heap.insert(9)
heap.insert(6)
heap.insert(50)
print(heap)
13. 다익스트라
// Dijkstra
// 최단경로 검색
// 최단경로 문제 타입 3가지
// 1. 단일출발 - 단일도착 탐색
// 2. 단일출발 - 모든도착 탐색
// 3. 전체쌍 최단경로 - 모든 쌍 최단경로 탐색
let graph: [String: [String: Int]] = [
"A" : ["B": 9, "C" : 1, "D" : 15],
"B" : ["E": 10],
"C" : ["B": 5, "E" : 3],
"D" : ["E": 10],
"E" : ["F": 7],
"F" : [:]
]
struct NodePriority: Comparable {
static func < (lhs: NodePriority, rhs: NodePriority) -> Bool {
lhs.priority > rhs.priority
}
var node: String = ""
var priority: Int = 0
}
func dijkstra(graph: [String: [String: Int]], start: String) -> [String: Int] {
var distances: [String: Int] = [:]
var priorityQueue = MaxHeap(NodePriority.init(node: start, priority: 0))
for key in graph.keys {
let value = key == start ? 0 : 2147483647
distances.updateValue(value, forKey: key)
}
while !priorityQueue.isEmpty() {
guard let popped = priorityQueue.pop() else { break }
if distances[popped.node]! < popped.priority {
continue
}
for (node, priority) in graph[popped.node]! {
let distance = priority + popped.priority
if distance < distances[node]! {
distances[node] = distance
priorityQueue.insert(NodePriority.init(node: node, priority: distance))
}
}
}
return distances
}
// 1.노드마다 인접한 간선을 모두 검사하는 과정 = 𝑂(𝐸)
// 2.우선순위 큐에 insert/pop 하는 과정 = 𝑂(𝑙𝑜𝑔𝐸)
// 다익스트라 시간 복잡도 = 𝑂(𝐸𝑙𝑜𝑔𝐸)
14. Kruskal 알고리즘
// 신장트리 - 모든 노드가 연결되어있으며, 사이클 발생x
// 최소 신장트리 - 간선 가중치의 합이 최소인 신장트리 (MST)
// 최소 신장트리를 찾는 방법 1. 크루스칼, 2. 프림
// Union-find 알고리즘 - rank 딕져너리를 추가로 만들어 사이클이 발생하는것 검사
// Find - Parent노드를 통해 Root node를 찾고 비교해서 노드들이 사이클이 생기는지 확인
// Union - 사이클이 생기지 않으면 합치는 연산
let vertices = ["A", "B", "C", "D"]
let edges = [
(5, "A", "B"),
(1, "A", "C"),
(10, "A", "D"),
(5, "B", "A"),
(3, "B", "D"),
(1, "C", "A"),
(8, "C", "D"),
(10, "D", "A"),
(3, "D", "B"),
(8, "D", "C"),
]
typealias edge = (Int, String, String)
func kruskal(vertices: [String], edges: [edge]) -> [edge] {
var mst: [edge] = []
var edges = edges.sorted { $0.0 < $1.0 }
var rank: [String: Int] = [:]
var parent: [String: String] = [:]
for vertice in vertices {
rank.updateValue(0, forKey: vertice)
parent.updateValue(vertice, forKey: vertice)
}
func find(_ node: String) -> String {
if node != parent[node]! { // 루트 노드 찾아야만 재귀 탈출
parent[node] = find(parent[node]!)
}
return parent[node]!
}
func union(_ nodeV: String, _ nodeU: String) {
let rankV = find(nodeV)
let rankU = find(nodeU)
if rankV > rankU {
parent[rankU] = rankV
} else {
parent[nodeV] = nodeU
if rankV == rankU {
rank[nodeU]! += 1
}
}
}
while mst.count < (vertices.count - 1) {
let node = edges.removeFirst()
if find(node.1) != find(node.2) {
union(node.1, node.2)
mst.append(node)
}
}
return mst
}
// 시간복잡도 O(ElogE)
15. Prim 알고리즘
// 프림알고리즘
// 그래프를 가지고 최소신장트리를 찾는방법
// 1 시작노드를 정하고 이를 '연결된 노드 집합'에 삽입
// 2 A와 연결된 간선들을 '간선 리스트'에 삽입
// 3 '간선 리스트'에 저장된 간선중 가장 가중치가 작은 간선을 꺼낸다
// 4 간선 AC의 도착지 C가 연결된 노드집합에 있다면 싸이클발생,'간선 리스트'에서 다른간선을 꺼낸다
// 5 간선 AC의 도착지 C가 연결된 노드집합에 없다면 해당 간선을 '선택 리스트'에 넣고 해당 노드를
// '연결된 노드 집합'에 넣는다
struct Edge: Comparable {
var start: String = ""
var dest: String = ""
var weight: Int = 0
init(_ start: String, _ dest: String, weight: Int) {
self.start = start
self.dest = dest
self.weight = weight
}
static func < (lhs: Edge, rhs: Edge) -> Bool {
lhs.weight < rhs.weight
}
}
let vertices = ["A", "B", "C", "D"]
let edges: [Edge] = [
.init("A", "B", weight: 5),
.init("A", "C", weight: 1),
.init("A", "D", weight: 10),
.init("B", "A", weight: 5),
.init("B", "D", weight: 3),
.init("C", "A", weight: 1),
.init("C", "D", weight: 8),
.init("D", "A", weight: 10),
.init("D", "B", weight: 3),
.init("D", "C", weight: 8)
]
typealias edge = (Int, String, String)
func prim(start: String, vertices: [String], edges: [Edge]) -> [edge]? {
var mst: [edge] = [] // 선택 리스트
var edgeList = MinHeap<Edge>() // 간선 리스트
var connectedNode: Set<String> = [] // 연결된 노드 집합
var adjacentEdges: [String: [Edge]] = [:] // 모든 노드에 연결된 모든 간선을 저장하는 딕셔너리
for vertice in vertices {
adjacentEdges.updateValue([], forKey: vertice)
}
for edge in edges {
adjacentEdges[edge.start]?.append(edge)
}
guard let startEdges = adjacentEdges[start] else { return nil }
connectedNode.insert(start) // 처음 선택된 노드를 선택 리스트에 삽입
for edge in startEdges { // 처음 선택된 노드에 대한 간선들을 간선 리스트에 삽입
edgeList.insert(edge)
}
while mst.count < vertices.count {
guard let poppedEdge = edgeList.pop() else { break }
if connectedNode.contains(poppedEdge.dest) { continue }
mst.append((poppedEdge.weight, poppedEdge.start, poppedEdge.dest))
connectedNode.insert(poppedEdge.dest)
guard let destEdges = adjacentEdges[poppedEdge.dest] else { return nil }
for edge in destEdges {
if !connectedNode.contains(edge.dest) {
edgeList.insert(edge)
}
}
}
return mst
}
// MinHeap
struct MinHeap<T: Comparable> {
var heap: Array<T> = []
var isEmpty: Bool {
return heap.count <= 1 ? true : false
}
init() { }
init(_ data: T) {
heap.append(data) // 0번 index 채우기용
heap.append(data) // 실제 Root Node 채우기
}
mutating func insert(_ data: T) {
if heap.isEmpty {
heap.append(data)
heap.append(data)
return
}
heap.append(data)
func isMoveUp(_ insertIndex: Int) -> Bool {
if insertIndex <= 1 { // 루트 노드일 때
return false
}
let parentIndex: Int = insertIndex / 2
return heap[insertIndex] < heap[parentIndex] ? true : false
}
var insertIndex: Int = heap.count - 1
while isMoveUp(insertIndex) {
let parentIndex: Int = insertIndex / 2
heap.swapAt(insertIndex, parentIndex)
insertIndex = parentIndex
}
}
enum moveDownStatus { case left, right, none }
mutating func pop() -> T? {
if heap.count <= 1 { return nil }
let returnData = heap[1]
heap.swapAt(1, heap.count - 1)
heap.removeLast()
func moveDown(_ poppedIndex: Int) -> moveDownStatus {
let leftChildIndex = (poppedIndex * 2)
let rightCildIndex = leftChildIndex + 1
// case1. 모든(왼쪽) 자식 노드가 없는 경우 (완전이진트리는 왼쪽부터 채워지므로)
if leftChildIndex >= (heap.count) {
return .none
}
// case2. 왼쪽 자식 노드만 있는 경우
if rightCildIndex >= (heap.count) {
return heap[leftChildIndex] < heap[poppedIndex] ? .left : .none
}
// case3. 왼쪽 & 오른쪽 자식 노드 모두 있는 경우
// case 3-1. 자식들이 자신보다 모두 작은 경우
if (heap[leftChildIndex] > heap[poppedIndex]) && (heap[rightCildIndex] > heap[poppedIndex]) {
return .none
}
// case 3-2. 자식들이 자신보다 모두 큰 경우 (왼쪽과 오른쪽 자식 중 더 큰 자식 선별)
if (heap[leftChildIndex] < heap[poppedIndex]) && (heap[rightCildIndex] < heap[poppedIndex]) {
return heap[leftChildIndex] < heap[rightCildIndex] ? .left : .right
}
// case 3-3. 왼쪽 & 오른쪽 중 한 자식만 자신보다 큰 경우
return heap[leftChildIndex] < heap[poppedIndex] ? .left : .right
}
var poppedIndex = 1
while true {
switch moveDown(poppedIndex) {
case .none:
return returnData
case .left:
let leftChildIndex = poppedIndex * 2
heap.swapAt(poppedIndex, leftChildIndex)
poppedIndex = leftChildIndex
case .right:
let rightChildIndex = (poppedIndex * 2) + 1
heap.swapAt(poppedIndex, rightChildIndex)
poppedIndex = rightChildIndex
}
}
}
}
16. Queue
// Queue = FIFO
// enqueue = 큐에 데이터를 넣는 작업
// dequeue = 큐에서 데이터를 꺼내는 작업
// front = 데이터를 꺼내는 쪽, 출구
// rear = 데이터를 넣는 쪽, 입구
struct Queue<T> {
private var queue: [T] = []
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? {
return isEmpty ? nil : queue.removeFirst()
}
}
var myQueue = Queue<Int>()
myQueue.enqueue(10)
print(myQueue)
myQueue.dequeue()
print(myQueue)
// index 가 있는 큐
struct Queue2<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
if head > 50 {
queue.removeFirst(head)
head = 0
}
return element
}
}
var myQueue2 = Queue2<Int>()
myQueue2.enqueue(10)
myQueue2.enqueue(20)
myQueue2.enqueue(30)
print(myQueue2)
myQueue2.dequeue()
print(myQueue2)
// 실습
struct q <T> {
private var queue : [T] = []
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? {
return isempty ? nil : queue.removeFirst()
}
}
var testQ = q<Int>()
testQ.enqueue(3)
testQ.enqueue(32)
testQ.enqueue(13)
print(testQ)
17. Stack
struct Stack <T> {
var stack: [T] = []
var count : Int {
return stack.count
}
public var isEmpty: Bool {
return stack.isEmpty
}
public mutating func push (_ element: T) {
stack.append(element)
}
public mutating func pop() -> T? {
return isEmpty ? nil : stack.popLast()
}
}
var myStack = Stack<Int>()
myStack.push(10)
myStack.pop()
18. Linked List
var greeting = "Hello, playground"
// 배열 : - 새로운 요소 삽입이 빠름 // 크기가 고정되고, 삭제 및 검색이 느림
// 연결리스트 : - 데이터 삽입 및 삭제 속도가 빠름 // 검색이 느리며 저장공간 효율이 낮음
class Node<T> {
var data: T? // Node의 값
var next: Node? // 다음 Node의 주소
init(data: T?, next:Node? = nil) {
self.data = data
self.next = next
}
}
class LinkedList<T:Equatable> {
private var head : Node<T>? // 첫노드는 없으므로 옵셔널
func append(data: T?) {
// 노드가 없을때 head가 첫노드를 가리킨다
if head == nil {
head = Node(data:data)
return
}
// 그렇지 않다면 노드의 마지막에 새로운 노드를 추가한다
var node = head
while node?.next != nil {
// 가장 마지막 노드로 접근하게한다
node = node?.next
}
// 마지막 노드에 도착한 node의 next에 새로운 노드를 추가한다
node?.next = Node(data:data)
}
func insert(data: T?, at index : Int) {
// 노드가 없을때 head가 첫노드를 가리킨다
if head == nil {
head = Node(data:data)
return
}
// 그렇지 않다면 노드의 마지막에 새로운 노드를 추가한다
var node = head
for _ in 0..<(index - 1 ){
if node?.next == nil { break }
node = node?.next
}
// 다음 다음 노드를 추가한다
let nextNode = node?.next
node?.next = Node(data:data)
node?.next?.next = nextNode
while node != nil {
// 정상통과하는지 확인 프린트
//print("index:", index )
print("index:", index ,"node:", node?.data ?? "x")
node = node?.next
}
}
func removeLast() {
if head == nil {return}
// 만약 현재 head 가 nil이면 다음 노드는 없으므로 nil
if head?.next == nil {
head = nil
return
}
// 다음 head를 현재노드로 가져온다
var node = head
while node?.next?.next != nil {
node = node?.next
}
node?.next = node?.next?.next
}
func searchNode(from data : T?) -> Node<T>? {
if head == nil { return nil }
var node = head
while node?.next != nil {
if node?.data == data {break; }
node = node?.next
}
return node
}
}
let linkedList = LinkedList<Int>()
linkedList.insert(data: 1, at: 0)
linkedList.insert(data: 2, at: 1)
//linkedList.insert(data: 3, at: 2)
Leave a comment