[알고리즘] 브루트 포스(Brute Force)

 

---

1. 브루트 포스 (Brute_force) 란?

2. 선형구조와 비선형구조   - 순차탐색, 깊이 우선 탐색, 깊이 우선 탐색

3. 브루트 포스의 문제점

---

|  브루트 포스 (Brute_force) 란?

 

브루트 포스는 암호 해독법 중 하나로,

 

Brute : 난폭한, 짐승같은
    +
Force : 힘

 

의 합성어로 난폭한 힘 으로 해석이 되는데,

무식할 정도로 1부터 100까지 정확하게 해독한다는 뜻이다.

 

다시말해, 모든 경우의 수를 전체탐색하는 암호 해독법이다.

 

전체 탐색하는 방법으로는 두가지로 나눌 수 있다.

 

 

 

|  선형구조와 비선형구조

 

전체 탐색에는 크게 선형구조(Linear) 와 비선형구조(Non Linear) 가 있다.

 

선형 구조는  데이터가 연속적으로 연결되어 있는 모양으로 전체적으로 탐색하는 순차 탐색이 있다.

 

 

 

비선형 구조는 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 형태로

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다.

깊이 우선 탐색(DFS)

 

 

너비 우선 탐색(BFS)

 

|  브루트포스의 문제점

 

하나 하나씩 대입해서 모든 경우의 수를 따지기 때문에 100%의 정확성을 보장하지만,

범위가 넓어질 수록 효율이 떨어진다.

 

예를들어,

// 1 ~ 100까지의 합을 구하라
int res = 0;
for (int i = 1; i <= 100; i++) {
    res += i;
}

1~100까지라면 범위가 좁기 때문에 금방 출력이 되겠지만

1억까지의 수 또는 그 이상의 수를 구하라고 한다면 그만큼 시간 복잡도가 늘어나게 된다.