"모든 가능성을 전부 다 시도하는 가장 단순하지만 확실한 방법"
브루트포스 알고리즘이란?
브루트포스(Brute Force)는
가능한 모든 경우를 일일이 다 시도하여 답을 찾는 알고리즘입니다.
"뇌 대신 힘으로 푼다!"는 말이 어울리는 방법입니다.
- 가능한 모든 입력을 직접 탐색해서 정답을 찾습니다.
- 수학적으로 '완전 탐색(Exhaustive Search)'이라고도 부릅니다.
- 최적화나 특별한 트릭 없이 문제를 정면으로 해결합니다.
왜 브루트포스가 필요한가?
"다 시도하는 거 비효율적이지 않나?"라고 생각할 수 있습니다.
하지만 다음과 같은 이유로 브루트포스는 여전히 중요합니다.
- 문제 크기가 작을 때는 최적의 방법
- 정답이 확실히 보장됨 (모든 경우를 다 보기 때문에)
- 디버깅이나 검증에 유용 (정답 체크용)
- 복잡한 문제를 단순화할 수 있음
- 다른 알고리즘의 기초가 되는 경우가 많음 (예: 백트래킹, 최적화)
실제 코딩 테스트나 초창기 프로토타입 개발에서도 많이 사용됩니다.
브루트포스 알고리즘 동작 방식
브루트포스는 모든 가능한 조합이나 경우를 순회하며,
각 경우마다 조건을 검사해 정답을 찾습니다.
기본 흐름
- 가능한 모든 경우를 생성한다.
- 각 경우를 하나씩 꺼내 조건을 검사한다.
- 조건을 만족하면 답으로 기록한다.
- 모든 경우를 다 검사할 때까지 반복한다.
예시 코드 (Python)
# 1부터 100까지 중, 2개 숫자의 합이 50이 되는 쌍 찾기
for i in range(1, 101):
for j in range(1, 101):
if i + j == 50:
print(i, j)1~100 사이의 모든 숫자 쌍을 다 시도합니다.
브루트포스의 장단점
장점
| 항목 | 설명 |
| 구현이 매우 쉽다 | 복잡한 알고리즘 지식 없이도 코딩 가능 |
| 항상 정답을 찾을 수 있다 | 모든 경우를 보기 때문에 실수 가능성 없음 |
| 문제 분석에 도움 | 문제의 본질을 직관적으로 파악할 수 있음 |
단점
| 항목 | 설명 |
| 시간 복잡도가 매우 높다 | 경우의 수가 기하급수적으로 늘어남 |
| 대규모 데이터에 불리하다 | 시간 초과(TLE) 발생 가능성 높음 |
| 메모리 사용량도 커질 수 있다 | 경우의 수를 저장하는 경우 공간 복잡도 문제 발생 |
대표적인 브루트포스 문제 예시
비밀번호 찾기
- 비밀번호를 맞출 때 가능한 모든 조합을 시도해보는 것
- 예: 4자리 숫자(0000~9999) 전부 입력해보는 공격
조합/순열 생성
- 모든 조합 또는 순열을 만들어야 하는 문제
- 예: n개의 숫자 중 k개를 선택하는 모든 경우 출력
특정 조건을 만족하는 수열 찾기
- 주어진 조건을 만족하는 수열을 전부 시도해본다
- 예: N개의 숫자 중 합이 S가 되는 경우 찾기
완전 탐색 게임 문제
- 미로 찾기, 퍼즐 완성 등
- 가능한 모든 이동 경로를 시도하는 방식
브루트포스 최적화 전략
브루트포스를 무조건 "느린 알고리즘"이라고 단정할 필요는 없습니다.
몇 가지 전략을 통해 브루트포스도 현실적으로 사용 가능하게 만들 수 있습니다.
경우의 수 줄이기 (Pruning)
- 불필요한 경우를 미리 걸러낸다.
- 예: 합이 이미 초과한 경우 이후 탐색을 중단
def find_combination(arr, target):
for a in arr:
if a > target:
continue # target 넘으면 무시
for b in arr:
if a + b > target:
continue
if a + b == target:
print(a, b)조합/순열 라이브러리 활용
- Python에서는
itertools라이브러리를 사용해 코드 간결화 combinations,permutations등 제공
from itertools import combinations
arr = [1, 2, 3, 4, 5]
for comb in combinations(arr, 2):
if sum(comb) == 5:
print(comb)문제 크기를 제한하는 전제 조건 확인
- 문제에서 입력 크기가 작으면 브루트포스 사용 가능성 높음
- 예: "N ≤ 10" 같은 조건
병렬 처리
- 경우의 수가 크지만 독립적이면 멀티스레드, 멀티프로세싱 활용
- 예: 대규모 패스워드 크래킹 시 병렬로 탐색
마무리 정리
| 항목 | 요약 |
| 브루트포스 정의 | 가능한 모든 경우를 다 시도하는 알고리즘 |
| 강점 | 구현 간단, 항상 정답 보장 |
| 약점 | 느린 시간 복잡도, 대규모 문제에 불리 |
| 대표 문제 | 비밀번호 맞추기, 조합/순열 문제, 경로 탐색 등 |
| 최적화 방법 | 가지치기, 경우의 수 줄이기, 병렬 처리 |
728x90