알고리즘 : 브루트 포스란

브루트 포스(Brute Force)란?

Brute : 무식한 + Force : 힘

가능한 모든 경우의 수를 탐색하면서 요구조건에 충족하는 결과를 가져온다

전체를 탐색하기 때문에 전체 탐색, 완전 탐색이라고도 한다. 브루트 포스 알고리즘은 해가 하나 이상 존재한다는 가정 하에 모든 범위를 탐색하므로 100% 정답을 찾을 수 있다

 

알고리즘을 설계하고 구현하는 것이 매우 쉽지만 실행 시간이 매우 오래 걸리며 메모리 측면에서 비효율적이다.

 

브루트 포스는 선형 구조와 비선형 구조로 나뉜다

- 선형 구조 : 순차 탬색

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

 

브루트 포스 예시

1. 5자리 비밀번호 자물쇠를 00000부터 99999까지 대입해서 자물쇠를 풀 수 있다.

 

 

2. 10의 약수의 합을 구하기 위해서는 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}에서 10의 약수만 남겨두고 구한다.

int sum = 0;
for(int i = 1; i <= n; i = i + 1)
   if(n % i == 0)
      sum = sum + i;

 

 

너비 우선 탐색, 깊이 우선 탐색, 백트래킹의 경우는 따로 포스팅을 진행하도록 하겠다.

우선 브르투 포스에 관한 기본 내용은 여기까지가 충분할 것이다

문제를 풀면서 필요한 부분이 생기면 추후 추가하도록 하겠다.