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

Brute force 

: 무식한 힘

 

- 완전 탐색 알고리즘 : 가능한 모든 경우의 수를 탐색하여 요구조건에 충족되는 결과만을 가져온다.

 

장: 단순한 알고리즘으로 쉽게 구현 가능, 정확성 100%

단: 모든 경우를 탐색하여 시간 효율성이 떨어진다.

 

예시) N={a, b, c}에서 a가 들어가는 N의 부분 집합을 구할 때, 일단 N의 전체 부분 집합을 구한다

{a}, {b}, {c}, {ab}, {bc}, {ac}, {abc} 이중에서 a를 포함하는 부분집합만 골라 선택한다.

 

완전탐색 알고리즘 사용 전 고려사항

1. 가능한 경우의 수를 대략적으로 계산
2. 가능한 모든 방법 고려
3. 적용

 

완전탐색 알고리즘 구현 방식

1. Brute Force 기법 - 경우의 수 모두 테스트
2. 순열 (Permutation) - n개의 원소중에서 r개의 원소를 중복 허용 없이 나열
3. 재귀 호출 & 백트랙킹
4. 비트마스크
5. BFS, DFS