CS

Dijkstra’s Algorithm 구글 맵이나 애플 지도에서 다른 지역으로의 최소 거리나 최단 시간을 알려주는 것을 사용해보셨나요? 다익스트라 알고리즘(Dijkstra’s algorithm)은 GPS 네트워크 기반의 두 장소 간의 최단 거리를 찾는 데에 매우 유용합니다. 다익스트라 알고리즘은 그리디 알고리즘입니다. 그리디 알고리즘은 문제를 단계별로 해결하면서 해당 단계에서 가장 최선의 경로를 선택합니다. 이는 어떠한 경로에서는 비용이 더 많이 들 수도 있지만, 전체적인 비용은 더 낮습니다. 그럼에도 불구하고, 꽤 좋은 솔루션을 매우 빠르게 제시해줍니다. 다익스트라 알고리즘은 유방향 그래프나 무방향 그래프의 정점 사이에서 가장 짧은 경로를 제시해줍니다. 그래프에 정점이 주어져있다면, 이 알고리즘은 시작..

DFS(Depth-First Search) 이전 장에서는 다음 레벨로 가기 전에 모든 이웃 정점을 방문하는 너비우선탐색(BFS)에 대해서 살펴보았습니다. 이번 장에서는 그래프를 탐색하는 다른 알고리즘인 깊이우선탐색(DFS)에 대해 살펴보겠습니다. DFS는 다양한 곳에서 활용할 수 있습니다. 위상 정렬(Topological sorting) 사이클 탐지(Detecting a cycle) 미로 퍼즐과 같은 경로 찾기(Pathfinding) 희소 그래프(sparse graph)에서 연결된 컴포넌트 찾기 DFS를 수행하기 위해선, 주어진 출발 정점에서 시작하여 가능한 한 멀리까지 분기를 탐색하려고 합니다. 그리고 해당 지점에서는 백트래킹(한 단계 뒤로 이동)을 하고, 찾고자 하는 대상을 찾거나 모든 정점을 방문할..

BFS(Breadth-First Search) 지난 장에서는 객체들의 관계를 파악하기 위해 그래프를 사용하였습니다. 그래프는 정점(vertices)과 간선(edges)은 객체들 간의 관계를 표현합니다. 여러 알고리즘은 그래프의 정점을 탐색하거나 순회하기 위해 존재합니다. 이러한 알고리즘 중 하나는 너비 우선 탐색(BFS) 알고리즘입니다. BFS는 다양한 문제들을 해결할 수 있습니다. 최소 신장 트리를 만들 수 있습니다. 정점 간의 잠재적 경로를 찾을 수 있습니다. 두 정점 간 가장 짧은 경로를 찾을 수 있습니다. 신장 트리란 (Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리입니다. 그래프의 최소 연결 부분 그래프입니다. 최소 연결이므로 간선의 수가 가장 적습니다. n개의 정점을 가지는 ..

Graph 그래프는 물체 사이의 관계를 정의해주는 자료 구조입니다. 그래프는 모서리(edge)로 연결된 꼭짓점(vertices)들로 만들어져있습니다. Weighted graphs 가중치가 부여된 그래프에서 모든 엣지는 이 엣지를 사용하는 비용을 나타내는 가중치를 가집니다. 이러한 가중치는 꼭짓점 사이에 있어서 가장 저렴하거나 가장 짧은 경로를 선택할 수 있도록 해줍니다. 항공의 예시를 통해 비행 경로를 다양하게 하는 네트워크의 예시를 생각해봅시다. 위의 예시에서 꼭짓점은 주나 나라를 나타내고, 모서리는 지점 간의 경로를 나타냅니다. 각각의 엣지에 있는 가중치는 두 지점 간의 항공료를 나타냅니다. 이 네트워크를 통해 샌프란시스코에서 싱가폴로의 가장 싼 항공권을 결정할 수 있습니다. Directed grap..

Quick Sort 지난 장에서는 병합 정렬이나 힙 정렬과 같은 비교를 기반으로한 정렬 알고리즘에 대해 배웠습니다. 퀵 정렬(quick sort)이란 비교를 기반으로 한 알고리즘입니다. 합병 정렬과 비슷하게, 분할 정복을 사용합니다. 퀵 정렬의 가장 중요한 특징 중 하나는 중심점을 선택하는 것입니다. 중심점은 배열을 세 가지로 나눕니다. [ elements pivot ] 이번 장에서는 퀵 정렬을 사용하고, 여러 파티셔닝 전략들을 살펴볼 것입니다. Example public func quicksortNaive(_ a: [T]) -> [T] { guard a.count > 1 else { // 1 return a } let pivot = a[a.count ..

Heap Sort 힙 정렬은 힙을 사용하여 배열을 오름차순으로 정렬하는 비교 알고리즘입니다. 힙 정렬은 부분적으로 정렬된 이진 트리라고 정의된 힙을 활용합니다. 최대 힙에서는 부모 노드가 자식보다 커야 합니다. 최소 힙에서는 부모 노드가 자식보다 작아야 합니다. Example 정렬되지 않은 배열을 오름차순으로 정렬하기 위해 힙 정렬은 이 배열을 최대 힙으로 변환시켜야 합니다. 이 변환은 모든 부모 노드들을 내려가면서 올바른 자리에 도달하도록 합니다. 최대힙의 결과는 다음과 같습니다. 이를 배열로 표현하면 다음과 같습니다. 한 번의 shift-down 연산의 시간 복잡도는 O(log n)이기 때문에, 힙을 만들기 위한 총 시간 복잡도는 O(n log n)입니다. 배열이 오름차순으로 정렬되었는지 확인해봅시다..

Radix Sort 지금까지는 정렬을 할 때 비교를 통해 정렬을 진행했습니다. 기수 정렬(radix sort)이란 정수를 선형 시간으로 정렬하기 위한 비교하지 않는(non-comparative) 알고리즘입니다. 문제에 따라 매우 다양한 기수 정렬이 존재합니다. 이번 장에서는 기수 정렬의 최수 유효 자리(least significant digit, LSD) 변형을 조사하면서 기본 10진수에 대해 집중할 예정입니다. Example var array = [88, 410, 1772, 20] 기수 정렬은 정수의 위치 표기법에 의존합니다. 배열을 최하위 자리의 숫자(1의 자리)를 기준으로 버킷에 나눕니다. 이 버킷들을 순서대로 비운다면, 다음과 같이 일부 정렬된 모습을 볼 수 있습니다. array = [410, 2..

Merge Sort 합병 정렬은 정렬 알고리즘 중 가장 효율적인 알고리즘 중 하나입니다. O(n log n)의 시간 복잡도를 가짐으로, 일반적인 정렬 알고리즘 중 가장 빠른 속도를 가집니다. 합병 정렬은 분할정복(divide and conquer)이라는 아이디어에서부터 시작되었습니다. 이는 큰 문제를 풀기 쉬운 작은 단위로 나눈 뒤, 마지막 결과물에 해결책을 합치는 방법입니다. 합병 정렬은 ‘먼저 분할하고, 나중에 합병’하는 방법입니다. Example 정렬되지 않은 카드 더미가 있다고 가정해봅시다. 1. 먼저, 카드 더미를 반으로 나눕니다. 이제 두 개의 정렬되지 않은 카드 더미가 있습니다. 2. 더 이상 나눌 수 없을 때까지 카드 더미를 나눕니다. 결국엔 각 카드 더미엔 하나의 카드만 남게 될 것입니다..