Brute Force Search

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

암호학에서의 Brute force attack이 아닌 알고리즘으로서의 브루트포스이다.

이 알고리즘의 핵심은 완전탐색, 가능한 모든 경우의 수를 탐색하면서 요구에 부합하는 결과를 가져오는 것이다.

장점은 모든 경우를 검사하므로 100%의 확률을 가졌지만,

모든 경우를 검사하는 만큼 효율성이 떨어질 수 있다.

---

문제해결 방법

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

예제 및 알고리즘

백준 블랙잭

문제정리

카드의 개수 N(3 <= N <= 100)과 딜러가 지정한 카드의 합 M(10 <= M <= 300,000), 그리고 카드에 쓰여있는 수들이 입력된다.

카드의 개수 N(3 <= N <= 100)과 딜러가 지정한 카드의 합 M(10 <= M <= 300,000),
그리고 카드에 쓰여있는 수들이 입력된다.

M을 넘지 않으며 M에 최대한 가까운 카드 3장의 합을 출력한다.

입력으로 들어온 카드가 5, 6, 7, 8, 9 이고 딜러가 지정한 블랙잭(합)이 21이라고 해보자.

들어온 카드를 배열로 생각하면

sum1 = Card[0] + Card[1] + Card[2]
sum2 = Card[0] + Card[1] + Card[3]


		...


sum10 = Card[2] + Card[3] + Card[4]

이런식으로 나타낼 수 있다.

여기에서 sum1 ~ sum10 중에 21과 가장 가까운 합을 구하는 것이므로,

3장의 카드를 더한 합을 모두 탐색하는 브루트 포스의 예제라고 할 수 있다.

#include <stdio.h>
int main() {
	int N, M;
	int tmp, sum = 0;
	int num[100] = {0, };
    
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < N; i++)
    	scanf("%d", &num[i]);
        
    for (int i = 0; i < N; i++) {
    	for (int j = i + 1; j < N; j++) {
        	for (int k = j + 1; k < N; k++) {
            	tmp = num[i] + num[j] + num[k];
                if (tmp > sum && tmp <= M)
                	sum = tmp;
            }
        }
    }
     printf("%d\n", sum);
     return (0);
}