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

728x90

브루트 포스(Brute Force) 란?

Brute(무식한) + Force(힘)

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

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

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

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

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

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

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

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

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

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

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

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

순차 탐색

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

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

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

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

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

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

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

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

- 구현방법

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

- 장점

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

- 단점

경로가 매우 길 경우 탐색 가지의 증가에 따라 비교적 많은 기억 공간을 필요로 한다.
유한(finite) 그래프의 경우, 해가 존재하지 않는다면 모든 그래프를 탐색하고 실패로 끝난다.
무한(infinite) 그래프의 경우, 결코 해를 찾지도, 끝내지도 못한다.
DFS에 비해 복잡하다.

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

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

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

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

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

- 구현 방법

순환 호출 이용
명시적인 스택(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