부르트 포스(brute force)

부르트 포스 알고리즘

부르트 포스 알고리즘을 공부하기 전에 부르트포스의 사전적 의미를 알아보겠습니다.

Brute Force
Brute : 짐승 같은, 난폭한
Force : 난폭한 힘, 폭력
=>"짐승처럼 난폭하고 무식하게"

부르트포스는 완전탐색 알고리즘으로 조합 가능한 모든 경우를 모두 탐색하고 비교하며 원하는 답을 찾아냅니다.

이 알고리즘의 가장 강력한 장점은 항상 정확도 100%를 보장하는 점에서 가장 확실하게 적용된다는 점입니다.

부르트 포스를 사용하기 위해서는 해가 존재할 것으로 예상되는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법이 필요합니다.

부르트 포스에 사용되는 알고리즘을 알아보겠습니다.

선형 구조를 전체적으로 탐색하는 순차 탐색
비선형 구조를 전체적으로 탐색하는 DFS, BFS
비선형 구조에서의 부르트포스는 BFS를 더 많이 사용합니다.

이 포스트에서는 선형 구조를 탐색하는 유형의 문제인 백준 2798번을 풀어보겠습니다.

백준 2798번 바로가기

문제는 N장의 카드 중 3장을 선택하여 합한 결과가 M과 가장 가깝고 작은 수를 출력하는 것입니다.

이 문제를 보고 선형 구조인 배열에다가 N장의 카드를 입력받고 그 배열을 순차 탐색으로 3개의 종류의 카드를 중복없이 더해야 된다고 생각했습니다.

즉 for문을 3중으로 사용하면 될 것이라고 생각하였습니다. 단, for문을 사용하면 시간초과를 반드시 고려해주어야합니다.

문제에서 N이 100 이하의 수로 제한되어 있으므로 3중 for문을 사용한다고 해도 100 x 100 x 100으로 1,000,000으로 100만 제한시간 1초만에 풀어낼 수 있습니다.

그리고 max의 값을 지정해 매번 계산되는 값이 기존 max값보다 크고 M 이하의 수라면 업데이트를 해주면됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 [] cards = new int[N];
        st = new StringTokenizer(br.readLine()," ");
        
        for(int i = 0; i<N;i++)
            cards[i] = Integer.parseInt(st.nextToken());
        

        int max = 0, temp = 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++){
                    temp = cards[i] + cards[j] + cards[k];
                    if(temp <= M)
                        max = Math.max(max,temp);
                }
            }
        }
        System.out.println(max);

    }
}