브루트포스

브루트는 '무식한' 이라는 뜻이고 '포스' 는 힘으로 무언가 무식하게 힘으로 풀려고 하다는 의미
즉, 모든 경우를 탐색한다는 의미이다.

예를 들면 비밀번호 4자리를 알아내기 위해서 숫자 패드에 있는 0 ~ 9를 0000 ~ 9999 까지 조합하여 비밀번호를 알아낸다는 것이다.

따라서 장점은 다소 간단한 구조의 알고리즘을 통해 탐색을 반복하며 구현할 수 있다.

그러나 단점은 메모리 효율이 굉장히 떨어지고 구하려는 숫자가 커질 수록 시간복잡도 역시 마찬가지로 증가하고 따라서 알고리즘 수행 시간이 길어진다.

종류

선형 구조에 경우 순차 탐색이
비선형 구조에 경우 인접한 노드를 먼저 탐색하는 BFS와 가장 끝에 있는 노드로 탐색하는 DFS 가 있다.

• 순차 탐색은 말 그대로 해를 찾을 때 까지 선형적인 구조 전체를 순차적으로 탐색하는 것이다.
• BFS와 DFS는 선형 구조가 아닌 그래프와 같은 것들에서 전체를 탐색할 때 사용하는 것이다.

구현 예시

https://www.acmicpc.net/problem/1436
백준 1436번 영화감독 숌 문제는 연속적으로 666이 오는 숫자들의 순번을 나타내는 문제로
666, 1666, 2666, 3666, 4666.... 에 대한 숫자들의 순번을 입력으로 받고 해당 숫자를 출력하는 문제이다.

#include <iostream>

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;

    int number = 0;
    int cnt = 0;

    while(n != cnt)
    {   
        number++;
        int temp = number;
        while (temp != 0)
        {
            if(temp % 1000 == 666)
            {
                cnt++;
                break;
            }

            temp /= 10;
        } 
    }
    cout << number;
    return 0;
}

시물레이션 방법

백준 1018번 : 체스판 다시 칠하기
https://www.acmicpc.net/problem/1018

    #include <iostream>
    #include <algorithm>

    using namespace std;

    int arr[50][50];
    int a[8] = {'B','W','B','W','B','W','B','W'};
    int b[8] = {'W','B','W','B','W','B','W','B'};

    int B_first(int n, int m)
    {
        int cnt = 0;

        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8;j++)
            {
                if (i % 2 == 0)
                {
                    if (arr[n + i][m + j] != a[j])
                        cnt++;
                }
                else
                {
                    if (arr[n + i][m + j] != b[j])
                        cnt++;
                }
            }
        }

        return cnt;
    }

    int W_first(int n, int m)
    {
        int cnt = 0;

        for(int i = 0; i < 8; i++)
        {
            for(int j = 0; j < 8;j++)
            {
                if (i % 2 == 0)
                {
                    if (arr[n + i][m + j] != b[j])
                        cnt++;
                }
                else
                {
                    if (arr[n + i][m + j] != a[j])
                        cnt++;
                }
            }
        }

        return cnt;
    }

    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int N, M;
        int cnt = 33;
        cin >> N >> M;

        for(int i = 0; i < N; i++)
        {   
            for(int j = 0; j < M; j++)
            {
                char k;
                cin >> k;
                arr[i][j] = k;
            }
        }


        for(int i = 0; i + 7 < N; i++)
        {
            for(int j = 0; j + 7 < M ; j++)
            {
                int temp = min(B_first(i,j),W_first(i,j));
                if (cnt > temp)
                {
                    cnt = temp;
                }
            }
        }
        cout << cnt;
        return 0;
    }

이 문제는 최대 50 x 50 까지의 체스판에서 8 x 8의 체스판이 검은색, 하얀색 둘 중 하나로 변을 공유하는 두 개의 사각형은 서로 다른 색을 가져야 한다.

BWBW
WBWB

이 문제의 풀이를 위해서 입력으로 받은 2차원 배열의 값들을 하나하나 확인해야 되는 브루트포스 알고리즘 방식으로 접근하였다.

결국 입력한 크기 안에서 만들어질 수 있는 8 x 8 에 대한 모든 경우를 탐색해야 되는데
입력한 크기 안에서 만들 수 있는 범위 안에서 서로 다른 시작점을 가진 8 x 8 을 탐색하기 위해선

그에 맞는 시물레이션 방법이 필요하다.

이를 위해 main 함수에서는 입력한 N 과 M 을 통해 반복문의 조건으로 N - 7 , M - 7 전 까지로 설정하여 8 x 8 을 만들 수 있는 범위를 설정한다.

그리고 B_first 와 W_first 함수에서는 넘겨준 인자를 통해 해당 지점을 시작점으로 간주해
8 x 8 을 탐색하게 된다.

이렇게 하여 입력한 범위 내에서 만들 수 있는 8 x 8 을 모두 탐색할 수 있게 된다.