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

완전 탐색 중 Brute Force 알고리즘에 대해 정리하였습니다.

1. 완전 탐색 (Exhaustive Search)

모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 방법입니다.
모든 가능성을 고려하므로 항상 최적의 해를 찾을 수 있지만, 경우의 수가 많은 경우 시간과 메모리의 부담이 커질 수 있습니다.

완전 탐색의 종류

• 브루트 포스
• 순열
• 백트래킹
• 비트마스킹
• DFS / BFS

2. 브루트 포스 (Brute Force)

말 그대로 “무식하게 힘으로 밀어붙이는 방식”의 알고리즘입니다.
가능한 모든 경우의 수를 탐색하여 정답을 찾는 방식입니다.
해당 알고리즘은 경우의 수가 작을 때 사용하는 것이 일반적입니다.
ex) 비밀번호가 000~999까지라고 할 때, 모든 숫자를 다 시도해서 맞추는 것 → 브루트 포스

시간 복잡도

가능한 모든 경우의 수에 따라 결정됩니다.
보통 O(n^k) 또는 O(k!) 으로 비효율적인 경우가 많습니다.

장점

• 설계하고 구현하기 쉬움
• 정확한 결과 보장

단점

• 가능한 경우의 수가 커질 경우, 시간이 매우 오래 걸릴 수 있음
• 메모리의 효율면에서 매우 비효율적

사용 조건

사용 시기	설명
N이 작고 경우의 수가 적을 때	일반적으로 N ≤ 10~15
문제의 조건이 복잡하지 않고 단순 비교로 해결 가능할 때	부분합, 조합 확인 등
빠른 구현이 필요하고, 최적화는 중요하지 않을 때	대회 초반 문제 등
정답을 무조건 찾아야 하고 최적화는 부차적일 때	패스워드, 수열 맞추기 문제 등

사용 예시

1. 반복문을 사용하는 경우

• 두 수의 합이 K인 쌍 찾기 (배열 내 모든 쌍 확인)

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == K) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

2. 재귀를 사용하는 경우

• 팩토리얼 계산

public class Main {
    public static void main(String[] args) {
        System.out.println(factorial(5));  // 5! = 5 * 4 * 3 * 2 * 1 = 120
    }

    public static int factorial(int n) {
        if (n == 0) {  // base case
            return 1;
        } else {  // recursion
            return n * factorial(n - 1);
        }
    }
}

재귀 함수 (Rebursion Function)

• 함수 내부에서 ‘자기 자신을 호출’하는 함수를 의미
• 함수가 자신을 반복적으로 호출하면서 원하는 결과를 도출할 수 있음
• 단, 함수 호출이 계속해서 쌓이기 때문에 호출 스택이 많아져서 성능이 저하될 수 있음
• 주의할 점
  1. 재귀문을 종료시키기 위한 종료 조건이 반드시 필요
  2. 현재 함수의 상태를 저장하는 parameter(인자)가 필요
  3. return문 신경 쓰기

---

참고 블로그

• Contributor9 - 완전 탐색 이해하기
• SpearDragon - 브루트포스 알고리즘