[Algorithm] Brute Force (브루트 포스)

Brute force (브루트 포스)

Brute (짐승[야수], 큰 동물) + Force (폭력, 힘)
직관적으로 무식하게 힘을 쓰는 알고리즘

 

Brute force (브루트 포스)

완전 탐색 알고리즘으로  가능한 모든 경우의 수를 탐색하고 조건에 충족되는 결과를 가져온다. 

처음부터 끝까지 무식하게 모두 탐색하여 결과를 찾기 때문에 100%의 확률로 정답을 출력한다. 

 

브루트 포스 알고리즘을 설계할 때는 '해가 하나 이상 존재한다'는 가정을 세우고 모든 범위를 탐색한다. 

 

 

브루트 포스 장단점

 

• 장점

설계하고 구현하기가 쉽다. 

100%의 확률로 정답을 구할 수 있다. 

 

• 단점 

알고리즘 실행 시간이 매우 오래 걸린다. 

메모리 효율이 매우 떨어진다. 

 

 

 

구조에 따른 브루트 포스의 2종류

 

선형 구조 - 순차 탐색

비선형 구조 - 백트래킹, BFS(넓이 우선 탐색), DFS(깊이 우선 탐색)

 

 

• 순차 탐색

리스트에서 특정한 값을 찾는 알고리즘, 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나간다. 

1) 주어진 문제를 선형 구조로 구조화한다. - 구조화
2) 구조화된 자료를 구조에 맞는 방법으로 해를 구성할 때까지 탐색한다. - 탐색
3) 탐색한 해를 주어진 문제에 맞게 정리한다. - 정리

 

• BFS(넓이 우선 탐색), DFS(깊이 우선 탐색)

[Algorithm] BFS, DFS

 

 

​

브루트 포스 알고리즘 문제 유형 리스트

 

'[Python] Baekjoon/Brute force(브루트포스)' 카테고리의 글 목록