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

브루트 포스

(brute : 무식한)

이름이 무식한 힘인데 이름답게 완전 탐색 알고리즘으로

컴퓨터의 빠른 연산능력을 이용해 나올 수 있는 모든 경우의 수를 탐색하여 조건에 충족하는 결과만을 추출한다.

 

→  고등학교 때 확률에서 경우의 수 배울 때 답을 잘 모르겠어서

     모든 경우의 수를 구해 답을 구하는 우리의 노가다를 생각하면 이해가 쉽다 ദ്ദി ´•ᴗ•ก)՞ ՞

 

선형구조를 전체적으로 탐색하는 순차 탐색,

비선현 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 기본적인 도구들이다.

 

브루트 포스 알고리즘의 장단점

장점 - 해답을 못 찾아낼 확률이 낮고 문제해결(설계)는 빠르게 할 수 있다.

          →  모든 경우의 수를 탐색하기에 충족조건만 틀리지 않았다면 예외가 발생하지 않는다.

단점 - 복잡도에 매우 민감하고 문제의 복잡도에 따라 자원이 기하급수적으로 필요해져 비효율적인 경우가 발생

          → 메모리 효율이나 실행시간 부분에서 효율성이 떨어진다.

          → ex. 4자리 비밀번호를 찾는데에 0000~9999까지 시도하게 되면 O(n^4)의 복잡도를 가지게 된다.

 

---

브루트 포스를 이용한 문제 해결 방법

1. 주어진 문제를 선형 구조로 구조화하기
2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색하기
3. 구성된 해 정리

여기서 선형 구조로 구조화하는 것은 컴퓨터가 문제를 해결할 수 있도록 정리를 하는 것이라고 생각하면 된다.

 

예시를 통해 알아보자

 

백준 4673번

1~10000 사이의 셀프 넘버를 찾는 문제로 1부터 10000까지 수를 모두 체크해야 하는 문제이다.

void selfnum(){
    int checkarray[10001]={0};
    int num=1;
    while(num<=10000){
        int testnum=num;
        int sum = testnum;
        while(testnum!=0){
            sum = sum+testnum%10;
            testnum/=10;
        }
        if(sum<=10000)checkarray[sum]++;
        num++;
    }
    for(int i=1;i<10001;i++){
        if(checkarray[i]==0)cout<<i<<"\n";
    }
}