[C++ 코딩테스트 공부] 브루트포스 알고리즘

브루트포스(Brute Force)

Brute(난폭한) + Force(힘)
모든 경우의 수를 탐색하며 요구조건에 충족되는 결과만을 가져오는 것

• 모든 영역 전체를 탐색하는것
• 깊이 우선(DFS), 너비우선(BFS), 순차 탐색 등을 사용한다.

• 문제 해결 방법

1. 백준 2798번 블랙잭

#include <iostream>
#include <cmath>

using namespace std;

#define Max 101

int BLJ[Max];

int blackjack(int N, int M)
{
    int sub = 100000;
    int sum = 0;
    for (int i = 0; i < N - 2; i++)
    {
        for (int j = i+1; j < N - 1; j++)
        {
            for (int k = j+ 1; k < N; k++)
            {
                if (sub > M - (BLJ[i] + BLJ[j] + BLJ[k])&& M - (BLJ[i] + BLJ[j] + BLJ[k]) >= 0 )
                {
                    sub = M - (BLJ[i] + BLJ[j] + BLJ[k]);
                    sum = BLJ[i] + BLJ[j] + BLJ[k];
                }               
            }
        }
    }
    return sum;
}

int main()
{
    int N, M;
    int Card;
    cin >> N >> M;
    for(int i = 0; i < N; i++)
    {
        cin >> Card;
        BLJ[i] = Card;
    }


    cout << blackjack(N,M);
}

3중 for문을 활용한 방법이다.
모든 경우의 수를 탐색하는 만큼 추가적인 조건을 추가해서 시간복잡도를 줄일 수 도 있다.

2.백준 7568번 덩치

#include <iostream>
#include <cmath>

using namespace std;
int height[51];
int weight[51];
int Compare[51];

void compare(int N)
{
    
    for(int i = 0; i< N; i++)
    {
        Compare[i] =1;
        for(int j = 0; j< N; j++)
        {
            if(height[i] < height[j] && weight[i] < weight[j])
            {
                Compare[i] = Compare[i] +1;
            }
        }
    }
    for(int i = 0; i< N; i++)
    {
        cout << Compare[i] << " ";
    }
}

int main()
{
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        cin >> weight[i] >> height[i];
    }
    compare(N);
    return 0;
}

2중 포문을 활용하여 비교값을 출력해주는 문제이다.