모각코 2회차 : 브루트포스 알고리즘 Brute Force Algorithm

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

"100억이 든 금고에 4자리 비밀번호를 풀 경우, 그 돈을 가질 수 있다면 어떻게 할 건가?"

이 질문에 나는 만약 시간 제한이 없다면 하나하나 다 대입해볼 것 같다.

이런 상황에 쓰이는 알고리즘이 브루트포스 알고리즘이다.

 

직역하면 무식한, 단순한 힘을 가지고 있는 알고리즘이며, 완전탐색 알고리즘이라는 이름으로도 알려져있다.

즉, 머리를 쓰지 않고 모든 것을 다 해보겠다는 의미를 가지고 있다. 

 

주로 비밀번호를 해킹할 때 사용되었던 용어인데

자주 사용되는 비밀번호, 생년월일, 기념일 등으로 유추를 해서 해킹하는 것이 아니라

비밀번호가 될 수 있는 모든 조합을 다 시도해 보는 기법인 Brute Force Attack이라고 불렸다.

 

예시 1 : 2798 - 블랙잭

코드

#include <stdio.h>

int main() {
    int n, m;
    int sum, max = 0;

    scanf("%d %d", &n, &m);
    int arr[n];

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            for (int k = j+1; k < n; k++) {
                sum = arr[i] + arr[j] + arr[k];
                if (sum > max && sum <= m)
                    max = sum;
            }
        }
    }

    printf("%d", max);
    
    return 0;
}

 

예시 2 : 2839 - 설탕 배달

코드

#include <stdio.h>

int main() {
    int n;
    int packages = 0;
    scanf("%d", &n);

    while (n >= 0) {
        if (n % 5 == 0) {
            packages += n/5;
            n %= 5;
            printf("%d\n", packages);
            break;
        }
        n -= 3;
        packages += 1;
    }

    if (n % 3 != 0) {
        printf("-1\n");
    }

    return 0;
}