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

Brute Force Algorithm - 브루트 포스 알고리즘

• 가능한 모든 경우의 수를 대입하여 탐색하는 완전 탐색 알고리즘

 

해가 존재할 수 있는 모든 경우를 집어넣어 결과를 확인하는 알고리즘이다.

브루트포스의 경우 특수한 알고리즘이라기 보단 누구나 생각할 수 있는 간단한 풀이방법에 가깝다.

 

예를 들어, 0~9까지 의 숫자 중 4자리 숫자를 맞추면 풀리는 자물쇠가 있다고 하자.

이 자물쇠에 관한 어떠한 힌트도 주어지지 않은 상태에서 자물쇠를 풀려고 하면

0000, 0001, 0002,... , 9998, 9999처럼 입력 가능한 모든 경우의 수를 시도하여

자물쇠가 풀릴 때 까지 반복해야 한다.

 

위와 같은 방식으로 문제를 해결하는 알고리즘을 브루트 포스 알고리즘이라 칭한다.

---

장점

1. 모든 경우에서 반드시 정답을 찾아낼 수 있다.
2. 복잡한 구조 없이 간단하게 구현할 수 있다.

1. 해가 존재할 수 있는 모든 영역을 탐색하기 때문에 누락되는 경우가 없다. 따라서 해가 존재하는 경우 반드시 정답을 찾아낼 수 있다.

2. 간단한 반복문이나 재귀 함수만 사용해서도 충분히 구현할 수 있다.

 

단점

1. 특정 상황에서 코드의 실행 시간이 비약적으로 상승할 수 있다.
2. 자원 관리에  비효율적이다.

1. 위에서는 4자리 자물쇠를 예로 들었지만, 10자리 숫자를 맞춰야 하는 자물쇠라면? 탐색할 경우의 수가 10¹⁰으로 증가한다. 이는 실행 시간의 증가와 직결되며 PS 중에는 시간 초과를 받는 경우가 발생한다.

2. 알고리즘 구현에 지나치게 많은 메모리를 필요로 하거나, 메모리에 값을 계속 누적하는 상황이 발생할 수 있다.

---

예시 코드

위에 예로 들었던 4자리 자물쇠를 푼다고 가정해 보자.

1번째, 2번째, 3번째, 4번째 자리의 숫자를 모두 대입해야 하므로 아래와 같은 코드로 구현할 수 있다.

#include<iostream>
using namespace std;
int main(){
    int ANS=1234,NOW;
    for(NOW=0; NOW<10000; NOW++){
        if(NOW==ANS) break;
    }
    cout<<NOW;
}

위 코드에서는 정답을 정수로 표기했지만 ANS [4]={1,2,3,4}와 같은 형태도 for 문을 중첩으로 사용해서 구현할 수 있다.

#include<iostream>
using namespace std;
int ANS[]={1,2,3,4},NOW[4];

bool CHECK(){
    // ANS 와 NOW 가 같은지 확인하는 함수
    // 일치하면 True, 다르면 False
}

void PRINT(){
    // NOW 배열을 출력하는 함수
}

int main(){
    int i,j,k,l;
    for(i=0; i<10; i++){
        NOW[0]=i;
        for(j=0; j<10; j++){
            NOW[1]=j;
            for(k=0; k<10; k++){
                NOW[2]=k;
                for(l=0; l<10; l++){
                    NOW[3]=l;
                    if(CHECK()){
                        PRINT();
                        return 0;
                    }
                }
            }
        }
    }
}

코드를 보면 바로 알 수 있듯이 for에 묶여있는 실행문이 짧음에도 불구하고

for 문을 중첩하여 사용하여 코드의 가독성이 떨어지며

배열의 값을 다른 방법으로 대입한다고 하여도 코드의 실행시간 자체는 변하지 않는다.

---

예제

[BOJ] 1018 - 체스판 다시 칠하기 (S4)

[BOJ] 1436 - 영화감독 숌 (S5)