[알고리즘] 브루트 포스(Brute Force) 알고리즘

완전탐색 브루트 포스 알고리즘이란?

---

브루트 포스를 직역한다면 브루트(Brute) 무식한 + 포스(Force) 힘

즉, 모든 경우의 수를 무식하게 탐색한다는 것이다. 전체를 탐색한다는 의미해서 전체 탐색, 완전 탐색이라고도 한다.

 

브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 정답을 찾을 수 있다.

 

선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, Breath First Search)이 가장 기본적인 도구이다.

 

DFS와 BFS는 그래프 알고리즘을 정리할 때 다루어보자.

 

브루트 포스의 장점과 단점

---

장점

• 알고리즘을 설계하고 구현하기 매우 쉽다.
• 복잡한 알고리즘 없이 빠르게 구현할 수 있다.
• 모든 경우를 다 고려하기 때문에 확실한 정답을 찾을 수 있다.

단점

• 알고리즘의 실행 시간이 매우 오래 걸린다.
• 모든 경우를 다 고려하기 때문에 비효율적이다.

 

브루트 포스 관련 예제

---

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

풀이

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

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int N = s.nextInt();
        int M = s.nextInt();

        int[] arr = new int[N];
        int max = 0;

        for(int i = 0; i < N; i++)
            arr[i] = s.nextInt();

        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 total = 0;
                    total = arr[i] + arr[j] + arr[k];
                    if(total <= M && max < total)
                        max = total;
                }
            }
        }
        System.out.print(max);
    }
}

풀이 방법

카드 3개의 합을 구하기 때문에 3중 for문을 돌려야한다. 이를 이용해 전체 카드의 합을 구한 뒤 M에 제시된 값에 가장 가까운 값을 찾아 화면에 제시해준다.

 

예를들어 5종류의 카드 5, 6, 7, 8, 9중 3장을 뽑아 21에 가까운 값을 뽑는다고 하였을 때 나올 수 있는 값은

5 + 6 + 7

5 + 6 + 8

5 + 6 + 9

5 + 7 + 8

5 + 7 + 9

5 + 8 + 9

6 + 7 + 8

6 + 7 + 9

6 + 8 + 9

7 + 8 + 9 의 경우를 알 수 있고 21과 가장 가까운 값은 21인것을 확인할 수 있다.