NamS의 iOS일기

우선순위 큐는 힙구조로 이뤄져있죠 힙구조란 완전이진트리이고 정렬기준에맞춰서 최댓값이나 최솟값을 빠르게 찾아낼 수 있어요 새로운 노드를 넣을땐 제일 끝에서 추가해서 자신의 부모의 인덱스인 (index-1)/2와 비교해서 거꾸로 올라오면서 조건에 맞는지 비교하며 교체가 일어나구요 (logn) 삭제할 때는 제일 위부터 아래로 가면서 다시 정렬하면서 교체하는 과정이 일어나요 (logn) struct PriorityQueue { var heap: [T] = [] let ordered: (T, T) -> Bool init(ordered: @escaping (T, T) -> Bool) { self.ordered = ordered } /// 큐 뒤에 요소 추가 mutating func enQueue(_ element:..

아주 기본적인 정렬들을 공부해볼게요 대표적으로 거품정렬(Bubble Sort) 선택정렬(Selection Sort) 삽입정렬(Insertion Sort) 이렇게 3가지가 있구요 각각 특징과 구현을 해볼거에요 거품정렬 정렬과정 인접한 두 원소의 대소를 비교해서 자리를 교환하면서 정렬해요 시간복잡도 O(n^2) func bubbleSort(arr: [Int]) -> [Int] { var arr = arr for i in arr.indices { // i번 시도 for j in 1.. arr[j] { // 스왑 let temp = arr[j] arr[j] = arr[j-1] arr[j-1] = temp } } } return arr } 선택정렬 정렬과정 Index 0부터 차례대로 해당 순서에 원소 넣을 위치를..

스위프트에서 딕셔너리는 자바나 일반 자료구조에서의 HashTable과 같은 개념에요 key-value로 이루어져있고 데이터 간에는 순서가 없죠 우선 HashTable이 뭔지 부터 알아볼까요?? HashTable 이란 key와 value의 쌍으로 이루어진 데이터 타입이에요 매핑하기전 원래값을 key, 매핑후 데이터 값을 hash value(hash code)라고 하며 그 hash value를 배열의 index로 사용하고 그 index에 value를 저장해서 사용하는 방식이에요 Hash함수란 해시 함수는 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수 왜 사용할까요?? 특정 key값에 해당하는 데이터를 바로 찾을 수 있어요 평균 시간 복잡도 O(1) 최악의 경우는 O(n) - 모든..

오늘은 이렇게 검색어를 치면 그 단어를 포함한 단어를 보여주는 자동완성을 구현해볼거에요 구현 하는 방법은 여러가지가 있을 수 있겟지만! 우선 방대한 리스트가 있거나 유동적인 데이터라면 서버와 통신을 통해서 자동완성을 구현하는 방법을 택하는게 좋을 것 같다는 생각이 들어요 이 게시글은 적당량(?)의 데이터를 가지고 자동완성을 구현하는거에요 Trie...?? Trie가 뭔지 알고 가야겠죠? Trie 트리 자료 구조 이구요 아래 그림과 같이 생겼어요 (빨간점은 단어가 끝났음을 의미해요, 아래에 이 점이 왜 있는지 이유가 나와요) 문자열을 탐색할 때 단순하게 하나씩 비교하면서 탐색을 하는것보다 훨씬 효율적 빠르게 탐색이 가능하다는 장점 각 노드에서 자식들에 대한 포인터(참조)들을 배열로 모두 저장하고 있다는 점..