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

브루트포스 알고리즘은 완전탐색알고리즘의 하나이다.

해가 존재할 수 있는 모든 경우의 수를 탐색하는 방법으로 '무식한' 알고리즘이라고도 할 수 있다.

 

브루트 포스의 구현 방법으로는 다음과 같은 것이 있다.

• 순차 탐색 - 선형 구조를 전체적으로 탐색
• 깊이 우선 탐색(DFS)  - 비선형 구조를 전체적으로 탐색
• 너비 우선 탐색(BFS)  - 비선형 구조를 전체적으로 탐색
• 백트랙킹(backtracking) - 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법

 

브루트 포스의 장점

 - 예외가 없이 100%의 정확성

 - 알고리즘의 설계와 구현이 간단

 

브루트 포스의 단점

  - 메모리를 비효율적으로 사용

  - 실행시간이 길다(시간복잡도가 높음)

 

 

>>> 백준의 1436번의 '영화감독 숌' 문제도 브루트 포스 알고리즘으로 푸는 문제이다.