브루트포스(Brute Force) 알고리즘 완벽 가이드 - 완전탐색, 코딩테스트 빈출개념, 주의사항, 원리, C, Java, Python 예시코드

브루트포스 알고리즘

 

  코딩테스트에서 가장 기본적이지만 중요한 알고리즘 중 하나가 바로 브루트포스 알고리즘(Brute Force)입니다. 브루트포스는 단순하면서도 직관적인 접근법으로, 풀이법을 찾기 어려운 문제를 해결할 때 유용하게 사용할 수 있습니다. 오늘은 브루트포스 알고리즘의 개념, 동작 원리(반복문과 재귀), 시간 복잡도, 장단점, 대표 문제와 함께 C, Java, Python 코드 예시를 정리하겠습니다.

---

1. 브루트포스 알고리즘이란?

브루트포스 알고리즘은 가능한 모든 경우의 수를 탐색하여 정답을 찾아내는 방법입니다. 완전탐색(Exhaustive Search)이라고도 불리며, 가장 단순하고 직관적인 접근 방식으로 문제를 해결합니다.

예를 들어, 숫자 자물쇠를 푸는 방법을 생각해볼까요? 가능한 모든 숫자 조합을 하나씩 시도해보는 것이 바로 브루트포스의 대표적인 예입니다.

중요! 브루트포스는 가능한 경우의 수가 적을 때만 사용해야 합니다. 경우의 수가 커지면 실행 시간이 급격히 늘어나므로 효율적인 알고리즘으로 대체해야 합니다.

---

반응형

2. 브루트포스 동작 원리

브루트포스 알고리즘은 반복문과 재귀를 이용하여 구현할 수 있습니다.

 

(1) 반복문을 이용한 구현

반복문은 가능한 모든 조합이나 배열을 생성하는 데 유용합니다. 단계별로 경우의 수를 하나씩 탐색하며 조건을 만족하는지 확인합니다.

예시: 3자리 숫자 자물쇠

def brute_force_lock():
    for i in range(1000):
        print(f"Trying password: {i:03d}")

 

(2) 재귀를 이용한 구현

 

재귀는 모든 경우의 수를 탐색하는 데 효과적이며, 특히 트리 구조나 순열/조합 문제에서 자주 사용됩니다. 현재 상태에서 다음 단계로 진입하며 조건을 체크합니다.

예시: 순열 생성

def generate_permutations(nums, current=[]):
    if not nums:
        print("Permutation:", current)
        return

    for i in range(len(nums)):
        generate_permutations(nums[:i] + nums[i+1:], current + [nums[i]])

이처럼 반복문과 재귀는 문제 유형과 데이터 구조에 따라 선택적으로 사용할 수 있습니다.

---

3. 브루트포스의 시간 복잡도

브루트포스의 시간 복잡도는 가능한 모든 경우의 수에 따라 결정됩니다. 보통 O(n^k) 또는 O(k!)와 같이 매우 비효율적인 경우가 많습니다.

예시 시간 복잡도:

• n개의 숫자에서 모든 순열을 탐색: O(n!)
• n개의 요소에서 k개를 선택하는 모든 조합 탐색: O(n^k)
• 단일 for문을 활용한 탐색: O(n)

---

 

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

장점:

1. 구현이 쉽다:
   • 복잡한 로직 없이 간단한 반복문으로 구현 가능.
2. 정확한 결과를 보장:
   • 모든 경우를 탐색하므로 정답을 반드시 찾을 수 있음.
3. 특정 문제에 강력함:
   • 입력 크기가 작거나 경우의 수가 적은 문제에 적합.

단점:

1. 비효율적:
   • 경우의 수가 많아질수록 시간이 기하급수적으로 증가.
2. 실제 응용이 제한적:
   • 입력 크기가 큰 문제에서는 사용하기 어려움.

중요! 완전탐색하려는 데이터 수가 작을 때만 사용해야 합니다. 입력 크기가 큰 경우에는 더 효율적인 알고리즘으로 대체해야 합니다.

---

 

5. 브루트포스 알고리즘 대표 문제

문제 1: 암호 자물쇠 열기

• 자물쇠의 비밀번호가 4자리 숫자일 때, 모든 조합을 시도해 정답을 찾는 문제.

문제 2: 부분 집합의 합

• 주어진 배열에서 모든 부분 집합을 탐색하여 특정 조건에 맞는 합을 찾는 문제.

문제 3: N-Queens 문제

• n × n 체스판에서 퀸이 서로 공격하지 않도록 놓는 모든 경우를 탐색하는 문제.

---

 

6. 예시코드

C 코드 예시: 암호 자물쇠 열기

#include <stdio.h>

void bruteForceLock(int n) {
    for (int i = 0; i < n; i++) {
        printf("Trying password: %04d\n", i);
    }
}

int main() {
    int maxPassword = 10000; // 4자리 숫자 자물쇠
    bruteForceLock(maxPassword);
    return 0;
}

---

 

Java 코드 예시: 부분 집합의 합

import java.util.*;

public class SubsetSum {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        int target = 5;
        findSubsets(nums, target);
    }

    public static void findSubsets(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < (1 << n); i++) { // 모든 부분 집합 탐색
            int sum = 0;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    sum += nums[j];
                }
            }
            if (sum == target) {
                System.out.println("Subset found with sum " + target);
            }
        }
    }
}

---

 

Python 코드 예시: N-Queens 문제

def is_safe(board, row, col, n):
    for i in range(row):
        if board[i] == col or \
           board[i] - i == col - row or \
           board[i] + i == col + row:
            return False
    return True

def n_queens(n, row=0, board=[]):
    if row == n:
        print("Solution:", board)
        return

    for col in range(n):
        if is_safe(board, row, col, n):
            n_queens(n, row + 1, board + [col])

n_queens(4)

---

 

브루트포스 알고리즘은 단순하지만 모든 경우를 탐색하므로 정답을 보장하는 강력한 방법입니다. 하지만 데이터 크기가 커지면 비효율적이므로, 입력 크기가 작은 문제에서만 활용해야 합니다.

 

 

같이 읽어보면 좋은 글

참고 1) 브루트포스에 메모이제이션(Memoization) 적용을 통한 성능 개선

2024.12.21 - [알고리즘] - 메모이제이션(Memoization) 적용을 통한 성능 개선 (1) - 브루트포스

메모이제이션(Memoization) 적용을 통한 성능 개선 (1) - 브루트포스

 

참고 2) 브루트포스, dfs, 백트래킹 비교

2024.12.20 - [알고리즘] - 브루트포스, DFS, 백트래킹 차이점 정리

브루트포스, DFS, 백트래킹 차이점 정리