[알고리즘] 브루트 포스(brute force)

Brute Force

영어를 해석해보면 brute : 짐승, 난폭한  force : 힘 으로 풀이되는데, Brute Force는 암호학과 알고리즘 관점으로 나눠서 이해할수있다.

 

암호학 관점에서의 brute force attack은 이론적으로 조합이 가능한 모든 문자를 하나씩 대입하여 암호를 해독하는 방식이다.

 

알고리즘 관점에서의 brute force search는 완전탐색 알고리즘을 이야기한다. 이 또한 가능한 모든 경우의 수를 모두 탐색하여, 원하는 요구조건에 충족하는 결과를 가지고 온다. 이 알고리즘은 모든 경우의 수를 대입하다보니 예외없이 100% 확률로 정답을 알수있다.

 

일반적인 방법으로 문제를 해결하려면 모든 자료를 탐색해야 하므로 특정한 구조를 전체적으로 탐색할수있는 방법이 필요하고, 이를 위해 해가 존재 할 것으로 예상되는 모든 영역을 전체 탐색하는 방식으로 알고리즘을 설계한다.

 

장점과 단점

장점

• 알고리즘을 설계하고 구현하는 것이 매우쉽다.
• 복잡한 알고리즘 없이 빠르게 구현이 가능하다.

단점

• 알고리즘의 실행시간이 매우 오래 걸린다.
• 메모리 효율면에서 굉장히 비효율적이다.

 

종류

브루트 포스는 크게 2가지의 구조로 나눌수 있다.

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

 

선형구조 문제 해결 방법

1. 주어진 문제를 선형 구조로 구조화 한다.

2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.

3. 구성된 해를 정리한다.

 

 

비선형구조 문제해결 방법

BFS / DFS

 

이개념을 바탕으로 문제에 적용해보자.