완전 탐색(Exhaustive Search)

컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법.
'무식하게 푼다'라는 의미인 Brute-Forece(브루트 포스)라고도 한다.
예를들어 1부터 100까지의 모든 수의 합을 구하시오. 같은 노가다 방법.

---

Brute-Force

• 어느 기법을 사용하지 않고 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법.
• 아주 기초적인 문제에서 주로 이용되거나, 전체 풀이의 일부분으로 이용.

---

백트래킹(Backtracking)

해를 찾는 도중에 해가 될 것 같지 않으면, 되돌아가서 다시 해를 찾는 방법.

• 해가 되지 않으면 그 경로는 쳐낸다.(가지치기) 이렇게 불필요한 경로를 쳐내기 때문에 효율적으로 문제를 처리할 수 있게 된다.
• 백트래킹으로 문제를 풀 경우, DFS로 모든 경우의 수를 탐색하다가 조건문 등을 걸어 해가 절대로 될 수 없는 상황을 정의하고 그런 상황일 경우 탐색을 중지하고 그 이전으로 돌아가 다시 다른 경우를 탐색하게끔 구현할 수 있다.

  깊이 우선 탐색(DFS)
  DFS는 가능한 모든 경로(후보)를 탐색한다.

---

DFS & BFS

대표적인 그래프 탐색 알고리즘
(1) 깊이 우선 탐색(DFS, Depth First Search)

• 정점의 자식들을 먼저 탐색하는 방식
• 한 개의 큐와 한 개의 스택을 사용한다.
• 미로 게임 등에서 경로가 존재하는지를 판별할때 유용

(2) 너비 우선탐색(BFS, Breadth First Search)

• 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
• 두개의 큐를 사용한다
• root와 가까운 노드들부터 찾기 때문에 최단거리를 탐색할 때 유용하다.
• 지도 어플에서 특정 위치까지의 최단거리 안내, 혹은 소셜미디어에서 친구 추천등에 이용.

DFS와 BFS는 모두 노드 수 + 간선 수 만큼의 복잡도를 지닌다. 즉, O(n)

언제 DFS, BFS로 풀어야할까?

• 검색 대상이 크다면 DFS, 크지 않으면 BFS
• 최단거리 구하는 문제는 BFS가 유리
• 경로의 특징(가중치) 저장해야 하는 문제는 DFS 유리

---