브루트 포스(Brute Force)

정의

brute: 무식한, force: 힘   무식한 힘으로 해석할 수 있다.

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

 

예제

1. 10의 약수의 합을 구하기

10의 약수가 될 수 있는 모든 자연수를 구조화 하자.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → 문제의 해가 될 수 있는 자료를 선형으로 구성하였다.

 

구조화된 자료가 선형 구조이므로 순차 탐색을 활용하여 첫 번째 원소부터 마지막 원소까지 탐색한다.

탐색하면서 10의 약수가 되는 값만 남겨두고 10의 약수가 될 수 없는 값을 배제한다.

10의 약수는 10을 현재 우너소로 나누어떨어지면 그 원소는 10의 약수이다.

위의 과정을 거치면 집합은 다음과 같이 정리된다.

{1, 2, 5, 10}

 

마지막으로 탐색결과를 정리하여 최종 해를 구한다.

1 + 2 + 5 + 10 = 18

 

2. 거스름돈을 지불할 수 있는 방법의 수와 최소 동전의 개수 구하기

10원과 50원으로 120원을 지불할 수 있는 모든 방법의 수와 최소 동전의 개수를 구해보자.

 

주어진 동전의 종류가 2가지이므로 2차원 즉 행렬의 형태로 구조화하여 일반적 방법으로 해결할 수 있다.

행을 50원, 열을 10원으로 생각하고 구조화해보자.

행렬

위 행렬에서 행렬(0, 0)은 50원 동전 0개, 10원 동전은 0개를 지불하는 방법으로 생각할 수 있다.

따라서 행렬(1, 7)은 50원 동전 1개, 10원 동전 7개로 120원을 지불하는 방법이 된다.

 

구조화하고 행렬을 2차원으로 탐색하여 120을 이루는 모든 경우의 수를 조사하여, 구한 값들 중 행의 값 + 열의 값의 합의 최소값을 찾으면 최소 동전의 수가 된다.

 

위 행렬을 탐색해 보면 120원을 지불할 수 있는 경우의 수는 (0, 12), (1, 7), (2, 2)의 3가지이며, 이들의 사용한 동전의 수는 각 행과 열의 합이다. 따라서 사용한 최소 동전의 수는 이 값들 중 최소값이므로 4이다.

 

120원을 지불할 수 있는 모든 경우의 수 : 3가지, 최소 지불 동전의 수 : 4개