[알고리즘] 브루트포스란?

브루트포스란?

Brute: 무식한

Force: 힘 

 

• 쉽게 설명하자면 무식한 힘을 갖는 알고리즘을 뜻한다. 
• 완전탐색으로 답을 찾는 알고리즘이며, 해당 알고리즘은 반복문과 조건문을 사용한다!

---

어떻게 동작하는가?

• 가장 유명한 문제로는 자물쇠 문제가 있다.
• 모든 수를 탐색하여 자물쇠를 푸는 비효율적이면서도 100% 정확도를 자랑하는 브루트포스의 대표적인 문제이다.

// 실제 비밀번호 (예: 1234)
int actualPassword = 1234;

// 4중 for문을 사용하여 모든 4자리 비밀번호를 탐색
for (int i = 0; i <= 9; i++) {
	for (int j = 0; j <= 9; j++) {
    	for (int k = 0; k <= 9; k++) {
        	for (int l = 0; l <= 9; l++) {
            	// 현재 시도 중인 비밀번호 생성
                int attempt = i * 1000 + j * 100 + k * 10 + l;

               	// 비밀번호가 맞는지 확인
                if (attempt == actualPassword) {
                	System.out.println("맞춘 비밀번호: " + attempt);
                    return; // 비밀번호를 찾았으므로 종료
                }
            }
        }
    }
}

---

 

시간 복잡도는?

• 단일 루프: O(n)
• 중첩 루프: O(n^2)
• 3중 루프 이상: O(n^k) (k는 중첩된 반복문의 수)
• 이므로 경우의 수가 많아질 수록 비효율적이다.

---

공간 복잡도는?

• 별도의 메모리 사용하지 않거나, 최소한의 메모리만 사용한다
• O(1) or O(n)

---

장단점은?

• 모든 경우의 수를 탐색하기 때문에 100%라는 정답률을 가지지만,
• 반대로 모든 경우의 수를 탐색하기 때문에 그만큼 높은 시간 복잡도를 필요로 한다.

---

마무리하며..

• 브루트포스를 이용한 백준 문제 [2798 - 블랙잭]을 풀며 글을 마치겠다.

 

[최종 코드]

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(), " ");
        ArrayList<Integer> arr = new ArrayList<>();

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {

            arr.add(Integer.parseInt(st.nextToken()));
        }

        int max = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {

                    int sum = (arr.get(i) + arr.get(j) + arr.get(k));

                    if (sum <= m && max <= sum)
                        max = sum;
                }
            }
        }

        System.out.println(max);
    }
}