브루트포스 알고리즘

브루트 포스 알고리즘은 모든 조건을 탐색하여 요구조건에 맞는 결과만을 가져옵니다.
즉 이 방법은 전체 경우의 수를 탐색하는 방법이기 때문에 어떤 방식이든 모든 경우의 수를 탐색한다면 브루트포스 알고리즘을 사용했다고 말할 수 있습니다.

1. 브루트 포스 종류

이 알고리즘은 자료의 구조에 따라서 2가지로 나뉘는데
선형구조 - 순차탐색
비선형구조 - DFS, BFS
가 있습니다.

DFS와 BFS는 뒤에서 다룰 내용이기 때문에 이번시간에는 순차탐색의 경우만 다루겠습니다.

2. 순차탐색

순차탐색 문제를 푸는 순서는 다음과 같습니다.

1.주어진 문제를 선형구조로 바꾼다.
2.자료들을 구조에 맞는 방법으로 해를 구할때까지 탐색한다.
3.탐색된 해를 문제출력조건에 맞게 출력한다.

위와 같이 문제를 풀면 한가지 단점이 있습니다.
모든 경우의 수를 탐색하기 때문에 숫자가 커지면 시간복잡도가 많이 늘어난다는 단점이 있습니다.
하지만 이 알고리즘을 써야지만 풀리는 문제가 있기 때문에 상황에 맞게 쓰면 됩니다.

대표 문제인 블랙잭 문제를 풀어보겠습니다.
https://www.acmicpc.net/problem/2798

3. 문제풀이

해당 문제는 카드 세장의 숫자합이 M을 넘으면 안되므로, 세 합이 M이 안넘을 경우일때 최대값을 비교하는 모든경우의 수를 고려하면 되는 문제입니다.
Java코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 카드의 개수
        int m = Integer.parseInt(st.nextToken()); // 초과하면 안되는 수

        int[] card = new int[n]; // N개의 카드 동적생성
        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++){ // 배열 안에 카드넣기
            card[i] = Integer.parseInt(st.nextToken());
        }

        int max = Integer.MIN_VALUE;
        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++){
                    int temp = card[i] + card[j] + card[k];
                    if(temp > max && temp <= m){ // 최대값이되, m을 넘지 않는 수
                        max = temp;
                    }
                }
            }
        }
        System.out.println(max);

    }
}

C++

#include <iostream>

#define endl '\n'
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m, card_num;
    cin >> n >> m;
    int card[n];
    for(int i = 0; i < n; i++){
        cin >> card_num;
        card[i] = card_num;
    }
    int max = -1;
    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++){
                int temp = card[i] + card[j] + card[k];
                if(temp > max && temp <= m){
                    max = temp;
                }
            }
        }
    }
    cout << max;
}