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

브루트(brute); 무식한, 야만적인, 맹목적인 + 포스(force); 힘

=> 발생할 수 있는 모든 경우를 다 따지며 해를 찾는다 = 완전 탐색

 

(ex. 비밀번호를 4자리로 설정한다고 할 때, 0000~9999를 다 탐색하여 암호를 해독한다.)

사용하는 경우

- 문제의 입력 크기가 작을 때 신속하게 결과 얻을 수 있다.

- 최적해를 찾을 때 모든 경우를 다 따져보므로 정확도는 굿

(but 경우의 수가 너무 많을 경우 실행시간이 너무 오래 걸리거나 메모리 효율 면에서 매우 비효율적일 수 있다.)

- 문제의 구조가 간단하고 직관적일 때 유용하다.

 

다시 정리하자면,

완전탐색의 장단점

장점

 

- 알고리즘을 구현하는 것이 상대적으로 쉽다.

- 복잡한 알고리즘 없이 빠르게 구현이 가능하다.

단점

- 알고리즘의 실행시간이 상대적으로 오래 걸린다.

- 모든 경우의 수를 탐색하기에 메모리를 비효율적으로 사용한다.

 

완전탐색의 종류

- 선형구조 : 순차 탐색

- 비선형구조:  DFS(스택, 재귀함수) / BFS(큐) / 백트래킹

 

(cf.백트래킹: 답 찾는 과정에서 이 경로가 아니라고 판단되면 버리고 다른 경로 탐색; 가지치기-pruning,

해를 찾는 도중 막히면 더 이상 깊이 들어가지 않고 이전 단계로 돌아가서 해를 찾아나가는 방법)

 

- 조합(순서 상관없이 요소 선택)

- 순열(순서 고려하여 나열하는 경우의 수)

- 재귀함수

 

 

참고

-----

https://st-lab.tistory.com/97

https://foreverhappiness.tistory.com/104

https://aiday.tistory.com/117