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

Challenge 1: BFS or DFS 다음 두 예에서, 두 노드(node) 사이에 경로(path)가 존재하는지 여부를 확인하는데 어떤 순회 방법(BFS, DFS)이 더 나은지 생각해 본다. A에서 F로 가는 경로(path) A에서 G로 가는 경로(path) Solution A에서 F로 가는 경로(path) : 찾고자 하는 경로가 그래프(Graph)에서 깊기 때문에 DFS(depth-first search)를 사용하는 것이 좋다. A에서 G로 가는 경로(path) : 찾고자 하는 경로가 Root에 가까이 있으므로, BFS(breadth-first search)를 사용하는 것이 좋다. Challenge 2: Recursive DFS 이전에는 DFS를 반복적(iterative)으로 구현 했다. 재귀(re..

이전 장(chapter)에서 다음 level로 넘어 가기 전에 해당 정점(vertex)의 모든 인접 정점(neighbor)을 탐색해야 하는 너비 우선 탐색(Breadth-First Search, BFS)을 살펴 보았다. 이 장(chapter)에서는 그래프(graph)를 탐색하거나 검색하기 위한 또 다른 알고리즘(algorithm)인 깊이 우선 탐색(Depth-First Search, DFS)을 살펴본다. DFS는 다음과 같은 문제를 해결하는 프로그램 작성에 사용할 수 있다. 위상 정렬(Topological sorting) 위상 정렬은 방향 그래프의 정점이 간선의 방향을 거스르지 않도록 나열하는 것을 의미한다. ex. 선수과목이 있는 대학 과목 https://ko.wikipedia.org/wiki/%EC%..

Challenge 1: Maximum queue size A에서 시작하는 위의 무방향 그래프(undirected graph)에서, Queue에 있는 최대 항목 수를 구한다. Solution 큐(Queue)에서 최대 항목의 수는 3이다. Challenge 2: Iterative BFS 이전에는 BFS를 반복적(iterative)으로 구현 했다. 재귀(recursive)로도 BFS를 구현할 수 있다. Solution extension Graph where Element: Hashable { func bfs(from source: Vertex) -> [Vertex] { var queue = QueueStack() //다음에 방문할 인접 정점을 추적한다. var enqueued: Set = [] //Queue에..

그래프(graphs)를 사용하여, 객체(objects) 간의 관계(relationships)를 표현하는 방법을 살펴 보았다. 객체(objects)는 정점(vertices)일 뿐이며, 객체 간의 관계(relationships)는 간선(edges)으로 표시된다. 그래프(graphs)의 정점(vertices)을 가로지르거나(traverse) 검색(search)하는 몇 가지 알고리즘(algorithms)이 있으며, 그 중 하나는 너비 우선 탐색(breadth-first search, BFS)이다. BFS는 다음과 같은 다양한 문제를 해결하는 데 사용할 수 있다. 최소 신장 트리(minimum-spanning tree) 생성 정점(vertices) 사이의 잠재적 경로(potential path) 찾기 두 정점(v..

Challenge 1: Count the number of paths 유향 그래프(directed graph)에서 두 정점(vertices) 사이의 경로(paths) 수를 계산하는 메서드(method)를 작성한다. 아래 예제 그래프(graph)는 A에서 E까지 5개의 경로(paths)가 있다. Solution 목표는 그래프(Graph)에서 두 정점(vertices) 사이의 경로(paths) 수를 찾는 함수(function)를 작성하는 것이다. 한 가지 해결책은 깊이 우선 순회(depth-first traversal)를 수행하고, 방문한 정점(vertices)을 추적(track)하는 것이다. extension Graph where Element: Hashable { public func numberOfPa..

SNS(social network)와 저가 항공권을 예약하는 것의 공통점은 두 모델 모두 그래프(Graph)로 나타낼 수 있다는 것이다. 그래프(Graph)는 객체(object) 간의 관계를 나타내는 자료구조(data structure)이다. 이는 간선(edge, edges)으로 연결된 정점(vertex, vertices)으로 이루어진다. 아래 그래프(Graph)에서 정점(vertex)은 원(circle)으로 표시되고, 간선(edge)은 정점(vertex)을 연결하는 선(line)이다. Weighted graphs 가중 그래프(weighted graph)의 모든 간선(edge)에는 이를 사용하는데 필요한 가중치(weight)가 있다. 이를 활용해 두 정점 사이에서 가장 저렴하거나(cheapest) 짧은(..

Challenge 1: Iterative quicksort 지금까지 퀵 정렬(quick sort)을 재귀적(recursively)으로 구현했다. 이와 달리, 구분 전략(partition strategy)을 사용해 퀵 정렬을 반복적(iteratively)으로 구현할 수 있다. Solution Lomuto’s partition strategy를 사용해 구현한다. 해당 함수는 배열(Array)과 low와 high를 매개변수로 받는다. 스택(Stack)을 사용하여, start와 end의 value 쌍(pair)을 저장한다. public func quicksortIterativeLomuto(_ a: inout [T], low: Int, high: Int) { var stack = Stack() //index를 저..

합병 정렬(Merge Sort)과 힙 정렬(Heap Sort)은 비교 기반 정렬 알고리즘(comparison-based sorting algorithm)이다. 퀵 정렬(Quick Sort)은 또 다른 비교 기반 정렬 알고리즘(comparison-based sorting algorithm)으로, 합병 정렬(Merge Sort)과 마찬가지로 분할 정복 전략(divide and conquer)을 사용한다. 퀵 정렬(Quick Sort)에서의 중요한 작업 중 하나는 피벗(Pivot)을 선택하는 것이다. 피벗(pivot)은 배열(array)을 세 개의 부분(partition)으로 나눈다. [ elements pivot ] Example public func quicksortNaive(_ a: [T]) -> [T]..

Challenge 1: Add heap sort to Array 배열(Array)에 heapSort() 메서드를 추가한다. 이 메서드는 배열(Array)을 오름차순(ascending)으로 정렬한다. Solution 배열(Array)에 힙 정렬(heap sort)를 추가하려면, Array의 요소가 Comparable을 구현해야 한다. 다른 부분은 이전에 구현한 힙(heap)과 매우 유사하다. extension Array where Element: Comparable { func leftChildIndex(ofParentAt index: Int) -> Int { (2 * index) + 1 } func rightChildIndex(ofParentAt index: Int) -> Int { (2 * index)..

힙 정렬(Heap Sort)는 힙(Heap)을 사용하여 오름차순(ascending order)으로 배열(Array)을 정렬하는 또 다른 비교 기반(comparison-based) 알고리즘(algorithm)이다. 힙 정렬(heap sort)은 정의에 따라, 다음과 같은 특징을 갖는 부분적으로 정렬된 이진 트리(binary tree)인 힙(heap)을 이용한다. 최대 힙(max heap)에서 모든 부모(parent) 노드(node)는 자식(child)보다 크다. 최소 힙(min heap)에서 모든 부모(parent) 노드(node)는 자식(child)보다 작다. Getting started 이전에 구현한 힙(Heap)을 활용한다. 여기서는 최대 힙(max heap)을 사용해, 정렬에 사용할 수 있도록 힙(..