여러분의 관심사와 흥미를 빅 데이터로 분석하여... 여러분의 관심사와 흥미를 빅 데이터로 분석하여...

Challenge 1: Binary search as a free function 이전에는 RandomAccessCollection 프로토콜을 extension해서 이전 탐색(binary search)을 구현했다. 이진 탐색(binary search)은 정렬된(sorted) Collection에서만 작동하므로, RandomAccessCollection의 일부로 해당 함수를 노출하면 오용될 가능성이 있다. 이를 방지하기 위해, 이진 검색을 일반 함수로 구현한다. Solution func binarySearch( for element: Elements.Element, in collection: Elements, in range: Range? = nil) -> Elements.Index? where Eleme..

이진 탐색(Binary search)은 시간 복잡도(time complexity)가 O(log n)인 가장 효율적인 검색 알고리즘(algorithm) 중 하나이다. 이것은 균형 이진 검색 트리(balanced binary search tree) 내에서 요소를 검색하는 것과 비슷하다. 이진 탐색을 사용하려면 다음 두 가지 조건을 충족해야 한다. Collection은 상수 시간(constant time) 내에 index 작업을 할 수 있어야 한다. 이는 해당 Collection이 RandomAccessCollection이어야 함을 의미한다. Collection은 정렬(sorted) 되어 있어야 한다. Example 선형 탐색(linear search)과 비교해 보면, 이진 탐색(binary search)의 ..

Challenge 1: How much faster? 자동 완성(autocomplete) 기능을 구현한다고 가정한다. 첫 번째 구현에는 간단한 문자열(string) 배열(Array)를 사용하고, 두 번째 구현에는 Trie를 사용한다. 데이터베이스에 총 100,000 개의 항목이 있고, "pri" 접두사(prefix)를 가진 4개의 항목 "prior", "print", "priority", "prius"이 포함되어 있을 경우, trie가 array에 비해 얼마다 더 빠른지 확인한다. 모든 O(1) 연산은 동일한 시간이 걸린다 가정한다. 따라서 n * O(1) == O(n) 이다. Solution Trie가 훨씬 빠르게 실행된다. 대략적인 추정 시간은 다음과 같다. 1,000,000 * 3 * O(1) / ..

Trie(try와 발음이 같다)는 영어 단어와 같이 콜렉션(Collection)으로 표현할 수 있는 데이터를 저장하는 데 특화된 트리(tree)이다. 문자열(String)의 각 문자(Character)는 노드(node)에 매핑된다. 각 문자열의 마지막 노드(node)는 종단 노드(terminating node)로 표시 된다(위의 이미지에서는 점을 찍어 표현한다). trie의 장점은 context의 접두사(prefix) 일치 여부 확인 시 가장 잘 설명할 수 있다. Example 문자열(String)의 접두사 일치(prefix) 여부를 확인하는 방법은 다음과 같다. class EnglishDictionary { private var words: [String] = [] func words(matching ..

Challenge 1: Number of leaves 높이(height)가 3인 완벽하게 균형 잡힌(포화) 트리(treeperfectly balanced tree)에는 몇 개의 잎(leaf) 노드(node)가 있는가? 높이(height)가 h인 완벽하게 균형 잡힌(포화) 트리(treeperfectly balanced tree)에는 몇 개의 잎(leaf) 노드(node)가 있는가? Solution 완벽하게 균형 잡힌 트리(perfectly balanced tree)는 모든 잎(leaf)이 같은 level에 있고, 그 level이 완전히 채워진다(포화 이진 트리). root만 있는 트리(tree)의 높이(height)는 0이다. 따라서 높이(height)가 3인 트리(tree)에는 8개의 잎 노드(leaf ..

이진 탐색 트리(binary search tree)에서 여러 연산의 시간 복잡도는 O(log n)이다. 하지만, 트리가 불균형 상태이면, O(n)까지 성능이 저하될 수 있다. 1962년, Georgy Adelson-Velsky와 Evgenii Landis는 최초의 self-balancing binary search tree인 AVL tree를 고안했다. Understanding balance 균형 트리(balanced tree)가 이진 탐색 트리(binary search tree)의 성능을 최적화하는 중요한 비결이다. 여기에는 세 가지 주요 균형 상태가 있다. Perfect balance 이진 탐색 트리(binary search tree)의 이상적인 형태는 포화(perfectly balanced) 상태이..

Challenge 1: Binary tree or binary search tree? 해당 이진 트리(binary tree)가 이진 탐색 트리(binary search tree)인지 확인하는 함수를 만든다. Solution 이진 탐색 트리(binary search tree)는 모든 왼쪽 자식(left child)이 부모보다 작거나 같고(??), 오른쪽 자식(right child)이 부모보다 큰 tree이다. -> 지금까지는 왼쪽 자식이 부모보다 작고, 오른쪽 자식이 부모보다 크거나 같도록 구현했었음. 트리가 이진 탐색 트리인지 확인하는 알고리즘에는 모든 노드를 순회해 이 속성들을 확인하는 과정이 포함되어야 한다. extension BinaryNode where Element: Comparable { va..

이진 탐색 트리(binary search tree, BST)는 빠른 조회(lookup), 삽입(insert), 제거(removal) 작업이 용이한 자료 구조(data structure)이다. 한 쪽을 선택하면 다른 쪽의 모든 가능성이 없어져, 문제를 절반으로 줄이는 의사 결정 트리(decision tree)를 고려해 볼 수 있다. 결정을 내리고 가지를(branch) 선택하면 뒤로 돌아갈 수 없다. 잎 노드(leaf node)에서 최종 결정을 내릴 때까지 계속 내려가야 한다. 이진 트리(binary tree)는 이와 같은 작업을 수행할 수 있다. 이진 탐색트리(BST)는 이진 트리에 두 가지 규칙을 추가한다. 왼쪽 자식(left child)의 value는 부모(parent)의 value 보다 작아야 한다...

이진트리(Binary Tree)는 알고리즘 인터뷰에서 굉장히 인기있는 주제이다. 이진트리에서의 순회(traversal) 방법에 대한 기초를 잘 갖추어야 할 뿐아니라 재귀 역추적(recursive backtracking)에 대한 이해가 필요하다. Challenge 1: Height of a Tree 주어진 이진 트리(Binary Tree)의 높이(height)를 계산한다. 이진 트리의 높이는 root와 가장 먼 leaf 사이의 거리로 결정된다. 단일 노드로 이뤄진 트리(Root밖에 없는 트리)는, root가 가장 먼 leaf이므로 높이는 0이 된다. Solution 재귀를 사용해 간단히 이진트리의 높이를 구할 수 있다. func height(of node: BinaryNode?) -> Int { guard..

자식 노드의 수에 제한이 없는 일반 Tree(트리)와 달리, Binary Tree(이진 트리)는 각 node에 최대 두 개의 자식이 있다. 이 자식들을 각각 위치에 따라 left, right라고 부른다. 이진 트리는 많은 트리 구조 알고리즘의 기초가 된다. Implementation public class BinaryNode { public var value: Element public var leftChild: BinaryNode? public var rightChild: BinaryNode? public init(value: Element) { self.value = value } } BinaryNode를 사용해 이진트리를 구현한다. var tree: BinaryNode = { let zero = B..