Test
큐(Queue)는 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 큐의 기능은 다음과 같다.enqueue(data) : 맨 뒤 데이터 추가하기dequeue() : 맨 앞 데이터 뽑기isEmpty() : 큐가 비었는지 안 비었는지 여부 조회Swift에서 아래와 같이 구현하면 사용할 수 있다.struct Queue{ private var queue: [T] = [] var count: Int{ return queue.count } // 데이터 추가 mutating func enqueue(_ data: T){ queue.append(data) } ..
스택은 제한적으로 접근할 수 있는 나열 구조이다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 및 후입선출(LIFO - Last In First Out) 구조로 되어 있다. 스택 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 접시 더미와 마찬가지로 추가 또는 제거는 상단에서만 실용적이다. 스택의 구조 푸시 및 팝 작업을 사용한 스택 런타임의 간단한 표현. 스택(stack)은 제한적으ko.wikipedia.org 스택은 후입선출(LIFO - Last In First Out), 가장 최근에 넣은 것을 먼저 뽑고 예전에 넣은 걸 늦게 뽑고 싶을 때 사용한다.스택의 기능은 다음과 같다.push(data): 맨 앞에 데이터 넣기pop() : 맨 앞 데이터 뽑고 그 데이터 제거pe..
병합 정렬(merge sort)는 배열을 나누어 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 아래는 두 배열을 비교하며 정렬하는 코드이다.func merge(_ array1: [Int], _ array2: [Int]) -> [Int] { var result: [Int] = [] var array1Index = 0 var array2Index = 0 while array1Index 이 코드는 N번 whle문이 작동하기 때문에 시간 복잡도는 O(N)이다. 코드만 보면 이것은 정렬하는 것이 아니라 정렬된 배열을 합치는 과정처럼 보일 수 있다. 분할 정복은(divide & conquer) 문제를 쪼개서 일부분들을 계속 해결하고, 어느새 전체가 해결되는 전략이다. 분할정..
버블 정렬(Bubble Sort)은 첫 번째 와 두 번째를, 두 번째와 세 번째를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째와 마지막을 비교하여 교환하면서 자료를 정렬하는 방식이다.func bubbleSort(array: [Int]) -> [Int]{ var array = array var cnt = array.count for i in 0.. array[j+1]){ array.swapAt(j, j+1) } } } return array} 첫 번째 for문에서 시간복잡도 O(N), 두 번째 for문에서도 시간복잡도 O(N) 만큼 소요되어 최종 시간복잡도는 O(N^2)이다.선택 정렬(Sele..
1 ~ 20 사이에 숫자에 14가 있는지 없는지 확인을 하기 위해 코드를 작성하는 중이다.let array = [Int](1...16)let num = 14func findNumIndex(_ array: [Int], _ num: Int) -> Bool { for n in array{ if(n == num){ return true } } return false} 만약에 이렇게 작성한다면 찾을 수 있겠다만 모든 배열의 수를 확인해보면서 찾아야하기 때문에 O(N) 만큼 시간복잡도가 걸릴 것이다.이것을 줄이기 위해 나온 방법이 이진 탐색(Binary Search)이다. 이진탐색은 최소값의 인덱스와 최대값의 인덱스 그리고 현재 인덱스를 잡고 시도했을 때..
LinkedList (연결 리스트)LinkedList 란 하나로 데이터 요소를 연결된 노드로 표현하는 방식 node(노드) : Linked List의 구성 요소, 데이터와 다음 노드가 무엇인지에 대한 정보(포인터)를 가지고 있음pointer(포인터) : 노드를 연결하는 역할. 각 노드는 다음 노드를 가르키고 있는 정보(포인터)를 가지고 있음head(헤드) : Linked List의 첫번째 노드를 가르키는 포인터data : 각 노드가 저장하는 실제 값 또는 객체Array vs LinkedList그러면 LinkedList와 우리가 평소에 사용하는 Array(배열)과 차이는 무엇일까? Array는 특정 index를 알고 있을 경우 데이터를 신속하게 접근할 수 있고, 새로운 요소 삽입이 빠르지만 크기가 고정되고..
