기초 알고리즘 요약

1. 그리디 알고리즘

 

현 상황에서 최적의 선택지를 선택하는 알고리즘. 단, 현 상황에서 최적의 선택이 전체 상황에서는 최적의 선택이 아닐 수 있다.

 

 

2. 완전탐색 ( Exhaustive Search, Brute Force )

 

가능한 모든 경우의 수를 일일히 탐색하는 방법. 무식하게 가능한 경우를 다 찾아보는 방식으로 Brute Force 알고리즘이라고도 불린다.

구현은 쉬우나 효율적인 알고리즘이라고 하기는 어렵다.

 

 

3. BFS

Breadth-First Search의 약자로, 너비 우선 탐색이라 불린다. 그래프의 시작 노드에 인접한 노드부터 탐색하는 알고리즘으로 노드를 넓게 탐색한다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용합니다.

 

 

4. DFS

Depth-First Search의 약자로, 깊이 우선 탐색이라 불린다. 갈 수 있는 노드까지 깊이 들어갔다가 더 이상 갈 수 있는 노드가 없으면 가장 가까운 갈림길로 돌아와 탐색하는 알고리즘으로 넓게 탐색하기 전에 깊게 탐색한다. 모든 노드를 방문하고자 하는 경우 이 방법을 사용한다.

 

 

5. 동적 프로그래밍