[JAVA] Brute Force 알고리즘

Brute Force ( 브루트포스 )

- Brute(무식한) + Force(힘)

영어 해석처럼 하나부터 열까지 모든 경우를 탐색하는 알고리즘이다.

모든 경우를 탐색하기 때문에 당연히 정답을 찾을 수 있다.

 

<장점>

• 알고리즘을 설계하고 구현하기 쉽다.
• 복잡한 알고리즘 없이 빠르게 구현 가능하다.

<단점> 

• 알고리즘 실행시간이 매우 길다.
• 메모리 효율면에서 매우 비효율적이다. 

<종류> 

• 선형구조 : 순차탐색
• 비선형구조 : 백트랙킹 , DFS , BFS

---

브루트 포스,,이름은 뭔가 멋있어 보이지만 복잡한 알고리즘을 푸는 경우 상당히 무식?한 방법!?

예시1 <백준 2789 - 블랙잭 >

브루트포스 알고리즘 사용 예시

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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());
        }

        Arrays.sort(cards); // 입력 배열을 오름차순으로 정렬

        int maxSum = 0; // M을 넘지 않으면서 최대한 가까운 카드 3장의 합을 저장
        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 sum = cards[i] + cards[j] + cards[k];
                    if (sum <= M) {
                        maxSum = Math.max(maxSum, sum);
                    }
                }
            }
        }

        System.out.println(maxSum);
    }
}

예시2 <백준 2789 - 블랙잭 >

투포인터 알고리즘 사용 예시

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

public class Baek_2789 {
    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[] A = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(A);
        int sum = 0;
        for(int i=0; i<n-2; i++) {
            int lt= i+1;
            int rt = n-1;
            while(lt<rt) {
                int answer = A[i] + A[lt] + A[rt];
                if(answer == m) {
                    sum = answer;
                    break;
                } else if (answer < m) {
                    sum = Math.max(sum,answer);
                    lt ++;
                } else {
                    rt --;
                }
            }
        }
        System.out.println(sum);
    }
}

문제에서는 브루트포스 알고리즘을 이용하여서 풀어도 별 지장이 없었지만, 더 복잡한 알고리즘을 요구하는 문제에서는 그러한 알고리즘을 사용하면 시간초과가 걸리기때문에 ,,
투포인터를 사용해서도 풀어봤다.

어려운 문제는 아니었지만, 그냥 넘어가지말고 다르게 생각해보는 습관을 키우자