작성: 2021-02-07 23:59
수정: 2021-02-20 23:39
난이도: Bronze Ⅲ

브루트 포스?

브루트 포스(Brute-forcing)는 알고리즘을 배울 때 가장 먼저 접하는 이름만 어려운 알고리즘이다. 그 이유는 가장 간단하고 구현하기 쉽기 때문이다. 브루트 포스의 과정을 보면 왜 그런지 알 수 있다. 위키피디아에 따르면 의사코드는 아래와 같다.¹

c = first(P)
while not c is None:
    if valid(P, c):
        output(P, c)
    c = next(P, c)

• P: 문제
• c: P의 해 후보
• valid(P, c): c가 P의 해인지 여부를 반환하는 함수
• output(P, c): 해를 출력하는 함수
• next(P, c): P에 대한 c의 다음 후보를 반환하는 함수

글로 풀어서 설명하면 아래와 같다.

1. 해의 후보 중 첫 번째를 가져옴
2. 모든 후보를 판별하기 전까지
   1. 현재 후보가 해이면 출력
   2. 다음 후보를 준비

또는 아래와 같이 쓸 수도 있다.

1. 모든 후보를 나열
2. 반복문 등으로 후보를 탐색하면서
   1. 현재 후보가 문제의 해이면 출력

또는 한 문장으로 설명하면 모든 경우에 대해 해인지 판별하는싹 다 때려박아보는 알고리즘이다.

성능

브루트 포스는 문제의 크기가 커지면 일반적으로 매우 느려진다. 모든 경우에 대해 조건을 판별하고 출력한다는 것은 상당히 비효율적이기 때문이다. 문제의 규모가 커지면 이 알고리즘을 사용해서 해를 구하는 것은 태양이 죽을 때까지 남은 시간보다 훨씬 오래 걸릴 수도 있다.

줄인다고 해도 알고리즘 자체를 바꾸지 않는 이상 많이 줄지는 않지만 조금이라도 문제의 크기를 줄이는 방법이 있다. 그 예시로는 N-queen 문제²가 있다. N×N 체스판 위에 N개의 퀸을 놓을 때 서로 공격하지 않는 위치에 놓는 경우의 수를 구하는 문제이다. 단순하게 브루트 포스를 적용시키려고 하면 _N²C_N 가지의 경우를 판별해야하므로 상당히 오래 걸린다. 하지만 퀸이 같은 가로줄에 있으면 불가능한 경우임을 알기 때문에 N개의 각 줄에 퀸을 하나씩 놓아 서로 공격하지 않게 만드는 문제로 필요없는 해 후보를 제거한다. 이렇게 하면 판별해야 할 경우의 수가 N^N 가지로 줄어든다.

예시(약수 구하기)

하나의 자연수가 주어졌을 때, 브루트 포스를 사용하여 이 수의 약수를 모두 찾는 과정은 아래와 같다.

for (int i = 1; i <= n; i++)
    if (n % i == 0)
        cout << i << " is divisor of " << n << endl;

코드를 위의 과정에 맞게 의미를 부여해보면 아래와 같다.

1. 1부터 n보다 작거나 같은 자연수까지 나열
2. 각 수를 반복문으로 탐색하면서
   1. n을 이 수로 나눈 나머지가 0이라면(즉, 약수라면) 출력

이게 진짜 알고리즘??

사실 브루트 포스는 알고리즘이라기에는 추상적이다. 알고리즘의 기본 요소인 입력과 출력이 정의되어있지도 않고 어떻게 무엇을 연산해야하는지도 알려주지 않는다. 다만 문제 해결의 접근 방식을 제시해주는 것 같기도 하다. 위의 예시와 같이 n의 약수를 구하는 문제는 ‘모든 경우를 준비해놓고 각 경우마다 조건을 만족하는 것을 확인하는 방법으로 풀 수 있다’는 식으로 문제 해결의 방법론을 제시하는 것이라 볼 수 있다. 이러한 것을 ‘패러다임’이라고 한다. 이러한 패러다임으로는 추후 다룰 동적 계획법이나 분할 정복법 등이 있다. 앞으로 이러한 패러다임의 경우 제목에 알고리즘이 아닌 (알고리즘)으로 분류를 할 예정이다.

요약

• 모든 경우에 대해 문제의 해인지 판별하는 알고리즘 일명 노가다
• 문제의 규모가 커지면 매우 느려짐
• 알고리즘은 아니고 알고리즘 패러다임(문제 해결의 접근 방법)

---

1. 위키피디아에는 수학적 표기법에 따른 의사코드로 나와있으나 작성자가 Python-스타일로 고침. ↩

2. 백준에 있는 문제이다(⑤ 9663 - N-Queen). 당연하지만 브루트 포스를 사용해서 제한 시간 내에 해결할 수는 없다. 백트래킹 기법을 사용해서 해결할 수 있는 문제이다. ↩

---