[Algorithm] Brute force 무작위 대입 알고리즘

[Algorithm] Brute force 무작위 대입 알고리즘

Brute force

무작위 대입 기법(Brute force)이란 말 그대로 될 때까지 수를 차례대로 대입하며 푸는 기법을 의미한다.

가장 간단하면서도 신뢰성, 정확성이 확실한 알고리즘 중 하나가 무작위 대입 기법(Brute force)이다. 암호해독, 해킹 관련해서 “무차별 대입 공격”이라고도 부른다고 한다.

이론상 모든 경우의 수를 다 검색해 보는 것이라 정확도가 100%라고 하며, 암호학에서는 가장 확실한 방법으로 통용되고 있다고 한다.

하지만 이렇게 간단하고, 신뢰성과 정확성이 보장되지만 범위, 길이에 따라서 기하급수적으로 경우의 수가 늘어나기 때문에 “자원”이 무지막지하게 쓰인다. ( 옛날 핸드폰의 비밀번호를 잊어버려 네 자리, 0000부터 9999까지 확인한다고 생각하면.. )

 

[BAEKJOON 2798 블랙잭]

단계별 알고리즘 문제에 무작위 대입 기법으로 푸는 문제 중 하나가 있어 잠깐 풀어봤다.

마찬가지로, 모든 경우의 수를 모두 대입, 비교하면 쉽게 풀 수 있는 문제다.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, m;
    int *arr;
    int tmp, max = 0;
    int i, j, k;

    scanf("%d %d", &n, &m);
    arr = (int *)malloc(sizeof(int) * n);

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

    for ( i=0 ; i<n && max<=m ; i++ )
    {
        for ( j=i+1 ; j<n && max<=m ; j++ )
        {
            for ( k=j+1 ; k<n && max<=m ; k++ )
            {
                tmp = *(arr + i) + *(arr + j) + *(arr + k);
                if ( tmp <= m && tmp >= max )
                {
                    max = tmp;
                }
            }
        }
    }

    printf("%d\n", max);

    return 0;
}

반복문을 이용하여 m에 가장 가까운 값에 도달하는 값을 찾고 출력한다. 앞에 말 했듯이 모든 경우의 수를 검색하여 결론을 도출해 내기 때문에 정확하지만 연산을 많이 하거나 자원이 많이 들어간다.

 

[BAEKJOON 2231 분해합]

#include <stdio.h>
#include <stdlib.h>

long getC(long number)
{
    long result = number;

    while( number/10 != 0 )
    {
        result += number%10;
        number = number/10;
    }
    result += number%10;

    return result;
}

int main()
{
    long n; // 어떤 값 입력
    long min;
    long i;

    scanf("%ld", &n);

    min = n;

    for( i=1 ; i<=n ; i++)
    {
        if( getC(i) == n )
        {
            if( min > i )
            {
                min = i;
            }
        }
    }

    if( min == n )
    {
        puts("0");
    }
    else
    {
        printf("%ld\n", min);
    }

    return 0;
}

getC() 라는 함수를 만들어 반복문에서 계속 호출하여 사용하고 있다. 역시 많은 자원을 소모한다.

 

[BAEJOON 7568 덩치]

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int count;
    int **person = NULL;
    int *info = NULL;
    int i, j;

    scanf("%d", &count);

    person = (int **)malloc(sizeof(int*) * count);

    for( i=0 ; i<count ; i++ )
    {
        // 두 개의 정보가 입력되어야 함(몸무게, 키, 랭크)
        info = (int *)malloc(sizeof(int) * 3);

        scanf("%d %d", info, (info+1));
        *(info + 2) = 0;

        // 더블 포인터의 값에 포인터를 넣음
        *(person + i) = info;

        info = NULL;
        getchar();
    }

    for( i=0 ; i<count ; i++ )
    {
        int rankCount = 0;
        for( j=0 ; j<count ; j++ )
        {
            // 몸무게와 키를 비교, 둘 다 크면 카운팅
            if( person[i][0] < person[j][0] && person[i][1] < person[j][1] )
            {
                rankCount++;
            }
        }
        person[i][2] = rankCount;
    }

    for( i=0 ; i<count ; i++ )
    {
        //printf("%d %d %d\n", person[i][0], person[i][1], ++person[i][2]);
        printf("%d ", ++person[i][2]);

        free(*(person + i));
    }
    
    free(person);

    return 0;
}

들어오는 모든 값에 키와 몸무게를 비교하여 등수를 매기면 된다. 이것도 모든 경우의 수를 비교하는 문제이므로 반복문으로 모든 수를 세서 등수를 매기면 된다.

 

[BAEJOON 1018 체스판 다시 칠하기]

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int x, y;
    int i, j, k, l;
    char **matrix;
    char * row;
    int minCount = -1;

    scanf("%d %d", &y, &x);

    // 체스판의 y축 먼저 생성
    matrix = (char  **)malloc(sizeof(char *) * y);

    getchar();

    for( i=0 ; i<y ; i++ )
    {
        // 체스판의 x축 생성
        row = (char *)malloc(sizeof(char) * x + 1);

        // 색깔 입력받고
        scanf("%s", row);

        //체스판에 row 추가
        *(matrix + i) = row;
    }

    // 체스판 8X8 로 잘라서 비교
    for( i=0 ; i+7<x ; i++)
    {
        for( j=0 ; j+7<y ; j++)
        {
            // 색깔 비교 홀/짝 비교
            int count = 0;
            int count1 = 0;
            int sw = 0;
            char first = matrix[j][i];

            for( k=0 ; k<8 ; k++)
            {
                // 1 Row 비교
                for( l=0 ; l<8 ; l++ )
                {
                    // sw 시작은 항상 0
                    if( k%2 == 0 )
                    {
                        if( sw == 0 )
                        {
                            if( matrix[j+k][i+l] != first )
                            {
                                count++;
                            }
                            else
                            {
                                count1++;
                            }
                            sw = 1;
                        }
                        else
                        {
                            if( matrix[j+k][i+l] == first )
                            {
                                count++;
                            }
                            else
                            {
                                count1++;
                            }
                            
                            sw = 0;
                        }
                    }
                    else
                    {
                        if( sw == 0 )
                        {
                            if( matrix[j+k][i+l] == first )
                            {
                                count++;
                            }
                            else
                            {
                                count1++;
                            }
                            
                            sw = 1;
                        }
                        else
                        {
                            if( matrix[j+k][i+l] != first )
                            {
                                count++;
                            }
                            else
                            {
                                count1++;
                            }
                            
                            sw = 0;
                        }
                    }
                    
                }
            }

            if ( count > count1 ) count = count1;
            if( minCount == -1 || minCount > count )
            {
                minCount = count;
            }
        }
    }

    for( i=0 ; i<y ; i++ )
    {
        free(*(matrix + i));
    }
    free(matrix);

    printf("%d\n", minCount);

    return 0;
}

경우의 수가 많아서 조금 헷갈린 문제였다. 위 문제를 가장 정확히 풀려면 처음 시작하는 색깔을 하나 정하고 count하는 것이 정확한 것 같았다.

 

무작위 대입 기법 예방

무차별 대입 기법은 “해킹”, “공격” 에서 많이 쓰이는 용어인 것 같다. 해당 블로그 서버의 로그를 보더라도 항상 누군가로부터 서버 침입을 하려하고 있다.

SSH Brute force
SSH Brute force
SSH Brute force
SSH Brute force

이처럼, 아무 ID에 아무 PW를 넣어 무차별로 대입하는데, 이러한 공격을 효율적으로 막을 수 있는 방법은 바로 “경우의 수를 무한히 늘리는 것”이다.

앞서 말 했다시피 모든 수를 비교, 연산하기 때문에 대상의 길이가 한자리 한자리 늘어날 때 마다 경우의 수는 기하급수적으로 늘어난다.

패스워드 설정 때 “최소 8자리 이상, 특수문자 포함” 이라는 사항도 위와같이 경우의 수를 늘려서 무차별 대입 공격에 예방하는 차원에서 하는 권고사항이다.

 

참고사이트

위키 – 무차별 대입 공격

%d 블로거가 이것을 좋아합니다: