1. 브루트 포스 (Brute-force) 알고리즘

모든 경우의 수를 탐색하는 완전 탐색 알고리즘

정확히는 완전 탐색 알고리즘의 한 종류지만, 완전 탐색 (전체 탐색) 그 자체를 뜻하는 의미로도 쓰입니다. 직역 하면 무식한(Brute) 힘(Force)으로, 모든 경우의 수를 탐색하여 100%의 정확도를 보장하나 높은 시간 복잡도를 가집니다. 최단 경로 찾기, 자물쇠 풀기 등 일상속의 많은 문제들을 해당 알고리즘으로 해결할 수 있습니다.

2. 사용 조건

1. 명확한 솔루션 정의

• 1부터 100까지의 숫자 중 합이 50이 되는 세 숫자를 구하라 (O)
• 가장 좋은 조합을 찾아라 (X)

문제에서 달성하고자 하는 솔루션, 문제의 조건을 만족하는 정답이 잘 정의되어 있어야 브루트 포스에서 도출된 솔루션이 올바른지 확인할 수 있습니다.

2. 유한하고 적당한 풀이의 수

문제에서 고려해야 할 솔루션의 수가 무한하거나 너무 크면 브루트 포스는 효율적이지 않습니다.

3. 사용 예시

• 선형 구조: 순차 탐색
• 비선형 구조: DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

DFS와 BFS는 이미 이전 포스트에서 다루었으므로, 순차 탐색에 관해서만 간단한 예시를 들어보겠습니다.

문제 해결 방법!

1. 주어진 문제를 선형 구조로 구조화
   : 문제를 푸는데 필요한 단계를 순서대로 정리합니다.

2. 구조화된 문제 공간을 적절한 방법으로 탐색
   : 가능한 모든 경우의 수를 하나씩 넣어보면서 해를 찾습니다.

3. 구성된 해를 정리
   : 찾은 정답을 정리해서 결과로 만듭니다.

1. 반복문 사용

브루트 포스 알고리즘의 대부분은 반복문과 조건문을 통해 답을 도출합니다.

10의 약수의 합을 구하라

1. 10의 약수가 될 수 있는 모든 자연수를 구조화
   : 1에서 10까지의 자연수를 선형으로 구성합니다. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

2. 순차 탐색을 활용하여 모든 원소를 차례대로 탐색하며 10의 약수가 될 수 없는 값을 배제합니다.
   : 최종 결과는 다음과 같습니다. {1, 2, 5, 10}

3. 탐색 결과를 정리
   : 1 + 2 + 5+ 10 = 18

이를 알고리즘으로 표현하면 이와 같습니다.

public class Main {
    public static void main(String[] args) {
        int n = 10;
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                sum = sum + i;
            }
        }

        System.out.println("약수의 합: " + sum);
    }
}

2. 재귀 함수 사용

10 팩토리얼을 구하라

10!은 1부터 10까지의 모든 자연수의 곱입니다. 반복문을 활용할 수 있으나, 재귀를 통하여 계산할 수도 있습니다.

public class Main {
    public static void main(String[] args) {
        System.out.println( "10!: " + factorial(10));

    }

    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

사진 출처: Brutto