브루트 포스(Brute Force)

브루트 포스란?

Brute = 짐승 같은, 난폭한

Force = 힘

 

조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 

흔히 암호학에서 연구되나, 알고리즘 분야에서도 사용되고 있다.

 

완전 탐색이라고도 한다.

 

 

타 알고리즘과 비교

예시로 500원 동전 한 개, 100원 동전 두 개, 50원 한 개 중 세 개를 골라 최댓값을 고른다.

 

그리디 알고리즘의 경우 가장 큰 단위의 동전을 먼저 뽑는다.

그렇기에 시간 효율이 좋다.

 

하지만 해당 문제를 브루트 포스로 해결할 경우 모든 경우를 탐색하기에

훨씬 많은 시간이 지체된다.

 

 

종류

배열, 리스트, 스택 큐, 덱

위와 같은 선형 구조는 순차 탐색을 한다.

 

백트랙킹, DFS, BFS

위와 같은 비선형 구조는 백트랙킹,  BFS(너비우선탐색) , DFS(깊이우선탐색), 를 사용한다,

 

백트랙킹

 

백트래킹은 현재 상태에서 다음 상태로 가는 모든 경우의 수를 찾아서 이 모든 경우의 수가 더 이상 유망하지 않다고 판단되면 이전의 상태로 돌아가는 것을 말한다.

 

재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드의 상태가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아간다.

 

 BFS와 DFS는 백트랙킹의 방식 중 하나이다.

 

 

BFS

모든 분기점을 다 검사하면서 진행하는 방식이다.

큐로 구현을 한다.

DFS

트리에서 바닥에 도달할 때까지 한쪽 방향으로만 내려가는 방식이다.

스택으로 구현을 한다.

 

추가 자료 https://creakycogwheel.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%8A%A4%ED%83%9D%ED%81%90%EB%A1%9C-%EC%9D%B4%ED%95%B4%ED%95%98%EB%8A%94-DFSBFS

 

사용 조건

문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다.

문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.

 

장단점

모든 경우의 수를 탐색하기 때문에 100%의 정확성을 갖지만

그만큼 시간 복잡도가 높다.