탐색공간의 배제(Exclusion of Search Space)
전체탐색에서 불필요한 공간을 탐색하지 않음으로써 알고리즘의 효율을 향상하는 방법
Algorithm
전체탐색법(Brute force)
주어진 문제에서 해가 될 수 있는 모든 가능성을 검사하는 방법
에라토스테네스의 체(Eratosthenes’s Sieve)
소수의 여부를 보다 효율적으로 알 수 있는 알고리즘
비선형 구조와 탐색(Non-linear Structure and Search)
비선형 구조가 무엇이고 이를 어떻게 탐색할 수 있는지 알아본다.
합병 정렬(Merge Sort)
O(nlogn)의 비교 기반 분할 정복 정렬 알고리즘
트리의 순회(Tree Traversal)
대표적인 트리의 순회 방법인 전위 순회, 중위 순회, 후위 순회를 알아본다.
선형구조와 탐색(Linear Structure and Search)
선형구조가 무엇인지 알아보고 순차탐색과 이분탐색을 활용하여 간단한 문제를 해결해 본다.
버블소트(Bubble Sort)
비교기반 정렬 알고리즘
다익스트라 알고리즘(Dijkstra Algorithm)- 예정 포스트
단일 출발정점 - 모든 도착정점 최단경로 알고리즘
SPFA(Shortest Path Faster Algorithm)
단일 출발 정점 - 모든 도착 정점 최단 경로 알고리즘
플로이드 와샬 알고리즘(Floyd Warshall Algorithm)-예정 포스트
모든 정점 쌍 최단경로 알고리즘
위상정렬(Topological sorting)
DAG에서 정점들의 위상순서를 결정하는 방법
그리디 알고리즘(Greedy Algorithm)-예정 포스트
현재의 상태에서 가장 최선인 것을 선택하여 전역 최적해에 도달하는 방법
너비우선탐색(Breadth First Search, BFS) - 구현
너비우선탐색을 이해하고 자바로 이를 구현 해본다.
너비우선탐색(Breadth First Search, BFS)
현재 레벨에서 인접한 정점을 모두 탐색하고 그 다음 레벨을 탐색하는 방법
깊이우선탐색(DFS) 구현 - Recursive
재귀 함수를 이용한 깊이우선탐색을 이해하고 자바로 이를 구현 해본다.
깊이우선탐색(DFS) 구현 - Iterative using stack
스택을 이용한 깊이우선탐색을 이해하고 자바로 이를 구현 해본다.
깊이우선탐색(Depth First Search, DFS)
트리나 그래프 자료구조를 탐색하는 알고리즘으로서 가지를 따라 가능한 한 깊게 탐색하고 원래의 지점으로 백트랙하여 다른 곳을 깊게 탐색하는 알고리즘
카운팅 소트(Counting sort)
특정 조건 하에 시간복잡도 O(n)이 걸리는 정렬 알고리즘
크루스칼 알고리즘(Kruskal’s Algorithm)
연결 가중치 그래프(Connected weighted graph)에서 최소 스패닝 트리(Minimum Spanning Tree)를 찾을 수 있는 그리디(Greedy) 알고리즘
선택 정렬(Selection Sort)
비교기반 제자리 정렬 알고리즘
퀵 소트(Quick Sort)
효율적인 비교기반 분할정복 정렬 알고리즘
삽입 정렬(Insertion Sort)
Stable and In-place 알고리즘
이분 탐색(Binary Search)
정렬된 배열(Sorted array)에서 찾고자 하는 값의 존재 유무나 위치를 로그적 시간에 찾는 알고리즘
Recursion
컴퓨터 과학에서의 재귀(Recursion)가 무엇인지 알아본다.