브루트포스 알고리즘 (완전 탐색 알고리즘)

브루트포스 알고리즘

---

Brute(무식한) + Force(힘) 브루트 포스는 완전 탐색 알고리즘으로,
가능한 모든 경우의 수를 탐색하고 조건에 충족되는 결과만을 가져옴!
무식하게 모든 경우를 탐색하기 때문에 100% 확률로 정답을 출력.
알고리즘이 기본적으로 해가 존재할 것으로 예상되는 범위를 탐색하기 때문에,
설계시 '해가 하나 이상 존재한다'는 가정을 세우고 모든 범위를 탐색! but, 시간이 오래 걸림!

브루트 포스의 종류

---

선형구조

순차탐색

비선형구조

BFS(넓이 우선 탐색),DFS(깊이 우선 탐색)

순차탐색

---

1) 주어진 문제를 구조화
2) 구조화된 공간을 적절한 방법으로 해를 찾을 때 까지 탐색

BFS,DFS 두 가지 모두 그래프를 탐색하는 방법!

그래프란?

node(정점)과 그 정점을 연결하는 edge(간선)으로 이루어진 자료구조의 일종.
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

.

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

---

출처 https://developer-mac.tistory.com/64

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택
ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

• 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
• 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

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

---

출처 https://developer-mac.tistory.com/64

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

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있음

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

DFS(깊이우선탐색) BFS(너비우선탐색)

현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색현재 정점에 연결된 가까운 점들부터 탐색

스택 또는 재귀함수로 구현

큐를 이용해서 구현

[https://codesyun.tistory.com/79](https://codesyun.tistory.com/79) [https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90](https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90) [https://developer-mac.tistory.com/64](https://developer-mac.tistory.com/64)