완전 탐색 - 브루트 포스(Brute Force)

브루트 포스?

브루트 포스(brute force)의 사전적 의미는 '무식한 힘'이다. 즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다. 
브루트 포스 알고리즘을 설계할 때는 '해가 하나 이상 존재한다.'는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

복잡한 알고리즘없이 빠르고 쉽게 구현이 가능하다는 장점이 있지만, 알고리즘의 실행시간이 오래걸리며 메모리 효율성이 떨어진다는 단점이 있다.

---

종류

• 선형 구조 : 순차탐색
  
• 비선형 구조 : 백트래킹, DFS, BFS

---

선형 구조 - 순차탐색

순차 탐색(Sequential Search)는 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘이다. 단방향으로 탐색을 수행하기 때문에 선형 탐색이라고도 부른다. 별도의 데이터 조작이 필요 없어서 단순하지만 그만큼 비효율적인 단점이 있다. 
순차 탐색 알고리즘은 최악의 경우 n번의 연산을 수행하며, 시간 복잡도는 O(n)이다.

---

비선형 구조 - 백트래킹

백트래킹(backtracking)은 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀해가며 해를 찾는 알고리즘이다. 해를 찾는 도중 현재 경로에서 해가 도출되지 않을 것 같으면 경로를 가지 않고 되돌아오기 때문에 반복문의 횟수를 줄일 수 있다.
불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미로 이 과정을 가지치기라 부르며 이 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 된다.

쉽게 말해 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
보통 DFS등의 알고리즘으로 모든 경우의 수를 탐색하는 과정에서 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그 상황일 경우 탐색을 중지시킨뒤 그 이전으로 돌아가 다른 경우를 탐색하게끔 구현한다.

---

비선형 구조 - 깊이 우선 탐색(DFS,Depth-First Search)

DFS는 탐색 트리의 수직 방향으로 점차 깊은 곳까지 해를 찾아 탐색해 나가는 알고리즘이다. 현 경로상의 노드들만 기억하면 되어서 저장공간의 수요가 비교적 작고, 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다는 장점이 있다.
얻어진 해가 최단 경로가 된다는 보장이 없고, 해가 없는 경로에 깊이 빠질 가능성이 있지만 이는 백트래킹으로 해결 가능하다.
모든 노드를 방문하고자 하는 경우에 이 방법을 선택하며 스택 또는 재귀함수를 사용하여 구현한다.

---

비선형 구조 - 너비 우선 탐색(BFS. Breadth-First Search)

BFS는 탐색 트리의 수평 방향으로 탐색을 하다가 더 이상 갈 수 없을 때 아래 노드로 이동하여 탐색을 반복하는 알고리즘이다. 주로 해를 찾는 최단 경로를 찾고 싶을 때 이 방법을 선택하며 큐를 사용하여 구현한다.
너비 탐색 알고리즘의 경우 그래프 탐색 시에 어떤 노드를 방문했었는지에 대한 여부를 검사하지 않으면 무한 루프에 빠질 위험이 있으므로 반드시 해야한다.