알고리즘 문제 풀이 스터디를 하며 만든 자료입니다.
개인 공부 기록용으로 올립니다.
🗝️ 비밀번호를 맞추는 가장 확실한 방법
비밀번호가 4자리 숫자일 때, 단서가 전혀 없다면 어떻게 풀어야 할까요?
0000부터 9999까지 전부 입력해보는 수밖에 없습니다.
이런 식으로 모든 경우의 수를 전부 시도하는 전략을
→ 브루트 포스(Brute Force) 혹은 완전 탐색이라고 합니다.
📌 브루트 포스(Brute Force)란?
// 0000 ~ 9999까지 모든 경우 탐색
for (let i = 0; i < 10000; i++) {
if (check(i)) { // 어떤 조건을 만족하면
console.log(`정답: ${i}`);
break;
}
}브루트 포스(Brute Force, 완전 탐색)는 가능한 모든 경우의 수를 탐색하여 조건을 만족하는 결과를 찾아내는 문제해결 패러다임입니다.
💡 Brute: 단순히, 순전히 / Force: 힘
→ 즉, 무식한 힘으로 가능한 모든 경우를 탐색하는 방법
브루트 포스를 쓰는 이유
✅ 장점
- 구현이 상대적으로 단순하고 직관적
- 정답이 존재하는 경우 반드시 찾게 됨
- 복잡한 조건이 있어도 적용 가능
❌ 단점
- 시간 복잡도에 매우 민감
- 입력 크기가 커질수록 실행 시간 급격히 증가
- 메모리 사용량이 클 수 있음
⚠️ N = 20인 경우 가능한 경우의 수는 약 100만개(2²⁰)가 되어버림
브루트 포스의 사용 조건
- 문제의 정답 조건이 명확해야 함
: 어떤 상태가 정답인지 판별할 수 있어야 함 - 가능한 경우의 수가 제한적이어야 함
: 솔루션의 수가 무한하거나 너무 크면 비효율적
✅ 언제 사용하면 좋을까?
-
입력 범위가 작은 경우
- N ≤ 20인 경우: 2^N ≈ 100만개 정도
- N ≤ 10인 경우: N! ≈ 300만개 정도
-
다른 알고리즘으로 해결하기 어려운 경우
- 복잡한 조건이 많아 수학적 공식화가 어려운 경우
- 문제의 패턴을 찾기 어려운 경우
-
확실한 정답이 필요한 경우
- 근사해가 아닌 정확한 답이 필요할 때
완전 탐색의 구현 방식
| 탐색 방식 | 설명 | 예시 |
|---|---|---|
| 단순 반복문 | 이중 반복문으로 모든 조합 탐색 | Two Sum 문제 |
| 부분집합 (Subset) | 포함/비포함 2가지 선택 | 비트마스크, 재귀 |
| 순열 (Permutation) | 원소를 일렬로 배치 | 순열 생성 |
| 조합 (Combination) | r개를 선택 | 조합 문제 |
| DFS/BFS | 그래프 등에서의 완전 탐색 | 미로 탐색 등 |
DFS, BFS, 백트래킹은 추후 자세히 설명
문제 해결 예시
1. 반복문 활용 - Two Sum
🔗 Leetcode - Two Sum
배열 nums와 목표값 target이 주어졌을 때, 두 수의 합이 target과 같아지는 두 원소의 인덱스를 반환
예제 :
nums = [2,7,11,15], target = 9
→ [0,1] (nums[0] + nums[1] = 2 + 7 = 9)
// 시간 복잡도 : O(N^2)
var twoSum = function(nums, target) {
const n = nums.length;
for(let i=0; i<n-1; i++){
for(let j=i+1; j<n; j++){
if(nums[i]+nums[j]===target) return [i,j]
}
}
return []
};모든 두 숫자 조합을 검사 → 시간복잡도 O(N²)
정확하지만 느릴 수 있음
재귀 활용 - 부분수열의 합
🔗 백준 - 부분수열의 합
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 반환
function solution(N,S,arr) {
let count = 0;
function dfs(index,sum){
if(index === N){
if(sum === S){
count++;
}
return;
}
dfs(index + 1, sum + arr[index]); // 포함
dfs(index + 1, sum); // 비포함
}
dfs(0,0);
// 크기가 양수인 부분 수열만 인정
if (S === 0) count--;
return count;
}
원소마다 포함/비포함(2가지 선택)
시간복잡도: O(2ⁿ)
마무리 요약
브루트 포스는 모든 경우의 수를 하나하나 다 시도해보는 방법입니다. 경우의 수가 적고, 무조건 정답을 찾고 싶을 때 강력한 전략이 됩니다.
브루트 포스만으로 풀 수 있는 문제는 드물지만, 어떤 문제든 '부분적 완전 탐색'이 필요한 경우는 매우 많습니다.
개인적으로 브루트 포스, 완전 탐색이라는 두 단어가 완전히 일치한 용어인가? 라는 질문이 들어서 시간이 걸렸던거 같습니다.
엄밀히 구분하는 일부 자료에서는 다음과 같이 의미상의 미세한 차이를 언급합니다.
| 용어 | 강조점 |
|---|---|
| 완전 탐색 | 모든 경우를 빠짐없이 찾는 "탐색 과정"에 중점 |
| 브루트 포스 | 정답을 무조건 찾기 위한 "시도 자체"에 중점 |
하지만 실전에서는 두 용어를 구별해서 쓸 필요는 거의 없고, 동의어로 여겨진다고 합니다.
Reference
