[Algorithm] 완전 탐색, 브루트 포스: 가장 단순한 알고리즘(Brute Force) 알아보기

 

한 사람이 단어를 생각하고 다른 사람이 그 단어를 추측하는 만약 "단어 맞추기" 게임을 한다면 추측하는 사람은 가능한 모든 단어를 시도하여 맞출 때까지 계속합니다.

 

예를 들어 추측하는 사람이 "축구"라는 단어를 맞춰야 할 때, 가능한 모든 단어를 시도하여 "축구"를 찾을 때까지 계속합니다. 이는 이번 포스팅에서 알아볼 브루트 포스 알고리즘의 아이디어와 비슷합니다.

 

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

Brute Force 실생활 예시

Brute : 무식한

Force : 힘

 

직역하면, 무식한 힘을 갖는 알고리즘입니다. 단어에서 알 수 있듯이 브루트 포스(Brute Force) 알고리즘은 문제 해결을 위해 가능한 모든 경우의 수를 시도하는 가장 단순하지만 강력한 방법입니다.

 

완전탐색(Exhaustive Search)이라고도 불리며, 모든 가능한 솔루션을 전부 탐색하여 정답을 찾습니다.

 

브루트 포스 알고리즘은 가능한 모든 경우의 수를 확인하며, 그중에서 최적의 해를 찾거나 원하는 조건을 만족하는 해를 찾을 때까지 반복합니다.

 

주어진 문제가 작고 해결하기 쉬운 경우에는 브루트 포스 알고리즘이 매우 유용합니다.

 

브루트 포스 알고리즘의 장단점

장점

1. 간단하고 직관적: 구현이 간단하며, 직관적으로 이해하기 쉽습니다.
2. 보편적인 적용 가능: 많은 종류의 문제에 적용될 수 있습니다. 특히 입력 크기가 작고 가능한 해의 수가 제한적인 경우에 유용합니다.
3. 항상 정확한 결과: 모든 가능한 경우의 수를 시도하기 때문에항상 정확한 결과를 제공합니다. 최적의 해가 항상 찾아지며, 검증된 답안을 얻을 수 있습니다.

단점

1. 대량 입력의 비효율성: 가능한 모든 경우의 수를 시도하기 때문에 입력 크기에 따라 실행 시간이 지수적으로 증가할 수 있습니다. 이는 매우 큰 입력에 대해서는 사용하기 어려울 수 있습니다.
   
   1. 또한 경우에 따라 불필요한 계산이 발생할 수 있습니다. 일부 경우에는 불필요한 중복 계산이 발생하거나 이미 검증된 부분을 다시 계산해야 할 수 있습니다.
2. 메모리 비효율성 

 

 

브루트 포스 사용조건

 

• 탐색 공간이 작을 때:
  • 가능한 해의 수가 비교적 적어 모든 경우를 시도해도 시간이 많이 걸리지 않을 때.
• 문제가 단순한 계산을 요구할 때:
  • 각 시도의 계산이 매우 간단하고 빠르게 수행될 수 있을 때.
• 정확한 해를 보장해야 할 때:
  • 해가 반드시 존재하며 모든 가능한 경우를 탐색하여 정확한 해를 찾아야 할 때.
  • 브루트 포스 알고리즘은 모든 가능한 경우를 시도하므로 정확한 해를 보장합니다.
• 제한 시간 내에 해결 가능할 때:
  • 문제의 제한 시간 내에 모든 가능한 경우를 시도할 수 있을 때.
• 다른 효율적인 알고리즘이 없을 때:
  • 문제를 해결할 수 있는 더 나은 알고리즘이 없거나, 존재하더라도 구현하기 매우 복잡할 때.
  • 간단한 문제에서는 복잡한 알고리즘보다 브루트 포스가 더 빠르고 간단할 수 있습니다.

 

 

완전 탐색 예시

public class BruteForceExample {

    // 브루트 포스 알고리즘으로 숫자를 찾는 메소드
    public static boolean findNumber(int[] arr, int target) {
        for (int num : arr) {
            if (num == target) {
                return true; // 찾은 경우 true 반환
            }
        }
        return false; // 찾지 못한 경우 false 반환
    }

    public static void main(String[] args) {
        // 주어진 배열
        int[] numbers = {1, 3, 5, 7, 9};

        // 찾을 숫자
        int target = 5;

        // 브루트 포스 알고리즘으로 숫자를 찾음
        boolean found = findNumber(numbers, target);

        // 결과 출력
        if (found) {
            System.out.println(target + "을(를) 찾았습니다.");
        } else {
            System.out.println(target + "을(를) 찾을 수 없습니다.");
        }
    }
}

 

위 코드는 배열에서 특정 숫자를 찾는 브루트 포스 알고리즘의 간단한 예시입니다.

 

findNumber라는 static 메서드를 선언합니다. findNumber는 배열과 , target을 인자로 받아 배열을 순회하면서 찾을 숫자인 target을 발견하면 true를 반환하고, 찾지 못한다면 false를 반환합니다.