[Algorithm] 브루트 포스와 BFS, DFS

브루트 포스(Brute Force) 란?

---

Brute(무식한) + Force(힘)

 

브루트 포스는 완전 탐색 알고리즘으로,

가능한 모든 경우의 수를 탐색하고 조건에 충족되는 결과만을 가져온다.

 

무식하게 모두 탐색하기 때문에 100%의 확률로 정답을 출력합니다.

알고리즘은 기본적으로 해가 존재할 것으로 예상되는 범위를 탐색하기 때문에,

브루트 포스 알고리즘을 설계할 때, '해가 하나 이상 존재한다'는 가정을 세우고 모든 범위를 탐색합니다.

 

100% 정답률을 가지며 만들기 쉽다는 장점이 있지만,

실행 시간이 오래 걸린다는 단점이 있습니다.

 

 

 

 

 

 

 

구조에 따른 브루트 포스의 종류

---

브루트 포스는 모든 자료를 탐색해야하기 때문에

어떤 구조더라도 전체를 탐색할 수 있는 방법을 가진다.

 

선형 구조를 전체 탐색하는 방법은 순차 탐색이 있고,

비선형 구조를 전체 탐색하는 방법은 BFS(넓이 우선 탐색), DFS(깊이 우선 탐색)가 있다.

 

 

 

 

 

 

 

순차 탐색

---

순차 탐색의 방법은 간단합니다.

 

① 주어진 문제를 구조화한다.

② 구조화된 공간을 적절한 방법으로 해를 찾을 때까지 탐색한다.

 

 

 

 

 

 

 

너비 우선 탐색 ( BFS, Breadth-Fist Search )

---

- 탐색 트리의 루트노드부터 목표노드까지 단계별로 횡방향으로 탐색하는 방식

- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택한다.

 

- 시작 노드에서부터 거리에 따라 단계별로 탐색하며, 재귀적으로 동작하지 않는다.

- 그래프 탐색 시 어떤 노드를 방문했었는지 여부를 검사해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.

 

- 구현방법

1. 큐(Queue) 를 이용 : 선입선출(FIFO) 원칙으로 방문한 노드들을 차례로 큐에 저장한 후 꺼낸다.

 

- 장점

• 출발노드에서 목표노트까지 최단 길이 경로를 보장한다.

 

- 단점

• 경로가 매우 길 경우 탐색 가지의 증가에 따라 비교적 많은 기억 공간을 필요로 한다.

• 유한(finite) 그래프의 경우, 해가 존재하지 않는다면 모든 그래프를 탐색하고 실패로 끝난다.

• 무한(infinite) 그래프의 경우, 결코 해를 찾지도, 끝내지도 못한다.

• DFS에 비해 복잡하다.

 

 

 

 

 

 

 

깊이 우선 탐색 ( DFS, Depth-First Search )

---

- 루트 노드(혹은 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

- 모든 노드를 방문하고자 하는 경우에 선택한다.

 

- 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.

- 그래프 탐색 시 어떤 노드를 방문했었는지 여부를 검사해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 수 있다.

 

- 구현 방법

1. 순환 호출 이용

2. 명시적인 스택(Stack) 사용 : 방문한 정점들을 명시적 스택에 저장하였다가 다시 꺼내어 작업한다.

 

- 장점

• 현 경로상의 노드들만 기억하면 되기 때문에 저장공간의 수요가 비교적 적다.

• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

- 단점

• 해가 없는 경로 속에 깊이 빠질 수 있다. 따라서 실제 경우에는 미리 정한 임의의 깊이까지 탐색하고 다음의 경로를 탐색하는 방법이 유용할 것이다.

• 얻어진 해가 최단 경로라는 보장이 없다. 해에 다다르면 탐색을 끝내므로, 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 얻어진 해가 최적이 아닐 수 있다.

• BFS에 비해 좀 더 간단하지만 느리다.

 

 

 

 

 

 

 

References

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89