[Algorithm] 전체탐색 : 브루트포스 알고리즘 (Brute Force Algorithm)

limchard·2024년 1월 18일

algorithm brute bruteforce force 반복 브루트포스 선형 선형구조 알고리즘

algorithm

목록 보기

1/2

완전탐색 : 브루트포스 알고리즘 Brute Force Algorithm

Brute : 무식한
Force : 힘

직역하면, 무식한 힘을 갖는 알고리즘이란 뜻으로, 가능한 모든 경우의 수를 모두 탐색하면서 결과를 도출한다.
전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.
브루트포스 알고리즘은 대부분은 반복문과 조건문을 통하여 답을 도출한다.

브루트포스의 장점

알고리즘을 설계하고 구현하기 쉽다
모든 경우의 수를 탐색하기 때문에 100% 정확성을 보장한다.

브루트포스의 단점

메모리 효율면에서 매우 비효율적이다.
알고리즘의 실행 시간이 매우 오래걸린다. (시간복잡도가 높다)

브루트포스 알고리즘의 사용 조건

1. 문제에서 달성하고 하는 솔루션이 잘 정의 되어 있어야 한다.

솔루션이 잘 정의되어 있지 않는 문제라면, 브루트 포스를 사용한 솔루션이 올바른지의 여부를 확인할 수 없다.

2. 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.

문제에서 고려해야할 솔루션의 수가 한정되어 있어야 한다. 고려해야할 솔루션의 수가 무한하거나 너무 크면 브루트포스 알고리즘은 효율적이지 않은 방법이다.

브루트 포스의 종류

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

비선형 구조는 추후 별도로 포스팅 하겠습니다.

선형 구조 문제 해결 방법

주어진 문제를 선형 구조로 구조화 한다.
구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
구성된 해를 정리한다.

브루트포스 예제

위와 같은 자물쇠를 다들 본적 있으리라 생각한다.
해당 비밀번호를 찾아보는 간단한 예제를 들어보려고 한다.
비밀번호는 내가 입력하는 방식으로 했다.

import java.util.Scanner;

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

        int a=sc.nextInt();
        int b=sc.nextInt();
        int c=sc.nextInt();
        int d=sc.nextInt();

        for (int i=0;i<10;i++){
            for (int j=0;j<10;j++){
                for (int k=0;k<10;k++){
                    for (int l=0;l<10;l++){
                        if (i==a&&j==b&&c==k&&d==l){
                            System.out.println("비밀번호는 "+i+j+k+l);
                        }
                    }
                }
            }
        }
    }
}