Brute Force Search
Brute Force Search (완전 탐색)
📝 개념 정의
가능한 모든 경우의 수를 다 검사하는 문제 해결법
특징: ✅ 항상 정확한 결과 도출 ❌ 다른 방법들보다 느림 ⚠️ 문제 크기 증가 → 시간 복잡도 증가
🔍 완전 탐색 기법
1. 단순 Brute-Force
for문과 if문으로 모든 case 생성
예시:
for i in range(n):
for j in range(n):
if condition(i, j):
result.append((i, j))
2. 비트마스크 (Bitmask)
각 원소가 포함/미포함 두 가지 선택으로 구성
사용 경우:
- 부분 집합 생성
- 조합 문제
예시: 백준 11732 집합
n = 3
for i in range(1 << n): # 2^n
subset = []
for j in range(n):
if i & (1 << j):
subset.append(j)
print(subset)
출력:
[]
[0]
[1]
[0, 1]
[2]
[0, 2]
[1, 2]
[0, 1, 2]
3. 재귀함수 (Recursion)
각 원소 포함/미포함 선택을 재귀로 구현
동작:
- 포함 → 원소 넣고 함수 호출
- 미포함 → 그 상태에서 함수 호출
예시: 피보나치 수열
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
4. 순열 (Permutation)
서로 다른 N개를 일렬로 나열하는 경우의 수
시간 복잡도: O(N!)
주의:
- 코딩 테스트에서는 다른 알고리즘 고려 필요
예시:
from itertools import permutations
arr = [1, 2, 3]
for perm in permutations(arr):
print(perm)
출력:
(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)
5. BFS/DFS
길 찾기 등에 주로 사용
DFS (Depth-First Search)
깊이 우선 탐색
구현:
- Stack 또는 재귀함수
- 최대한 깊숙이 들어가서 확인 후 다시 돌아가 다른 루트 탐색
탐색 순서:
1 → 2 → 4 → 8 → 5 → 9 → 3 → 6 → 7
BFS (Breadth-First Search)
너비 우선 탐색
구현:
- Queue 자료구조
- 가까운 노드부터 우선 탐색
탐색 순서:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9
📊 완전 탐색 기법 비교
| 기법 | 시간 복잡도 | 공간 복잡도 | 적합한 경우 | |------|-------------|-------------|-------------| | 단순 Brute-Force | O(n²) ~ O(n³) | O(1) | 작은 입력 | | 비트마스크 | O(2ⁿ) | O(1) | 부분 집합 | | 재귀함수 | 다양 | O(n) | 트리 구조 | | 순열 | O(n!) | O(n) | 순서 중요 | | BFS/DFS | O(V+E) | O(V) | 그래프 탐색 |
V = 정점 수, E = 간선 수
💡 완전 탐색 선택 가이드
단순 Brute-Force
사용:
- n이 작을 때 (n ≤ 1000)
- 간단한 조건 검사
비트마스크
사용:
- 부분 집합 문제
- n ≤ 20
재귀함수
사용:
- 트리 구조
- 백트래킹
순열
사용:
- 순서가 중요한 문제
- n ≤ 10
BFS/DFS
사용:
- 그래프 탐색
- 최단 경로 (BFS)
- 모든 경로 (DFS)
⚠️ 주의사항
시간 복잡도 고려
완전 탐색은 느림
n = 10: O(n!) = 3,628,800
n = 20: O(2ⁿ) = 1,048,576
n = 100: O(n²) = 10,000
→ 문제 크기에 따라 적절한 기법 선택
최적화 필요
완전 탐색 후 최적화:
- 동적 계획법 (DP)
- 그리디 알고리즘
- 분할 정복
❓ 면접 질문 예시
Q1. 완전 탐색이란 무엇인가요?
답변: 완전 탐색은 가능한 모든 경우의 수를 다 검사하는 문제 해결법입니다. 다른 방법들보다 느리지만 항상 정확한 결과를 도출합니다. 예를 들어 순열을 구하는 문제에서 완전 탐색은 가능한 모든 조합을 다 찾아봅니다.
Q2. 완전 탐색 기법에는 어떤 것들이 있나요?
답변:
- 단순 Brute-Force: for문과 if문으로 모든 case 생성
- 비트마스크: 부분 집합 생성
- 재귀함수: 트리 구조 탐색
- 순열: 순서가 중요한 문제
- BFS/DFS: 그래프 탐색 각 기법은 문제의 특성과 크기에 따라 선택해야 합니다.
Q3. 비트마스크는 언제 사용하나요?
답변: 비트마스크는 나올 수 있는 모든 경우의 수가 각 원소가 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우 사용합니다. 예를 들어 부분 집합을 생성하거나 조합 문제를 풀 때 유용하며, 시간 복잡도는 O(2ⁿ)입니다.
Q4. 순열의 시간 복잡도가 O(N!)인 이유는?
답변: 순열은 서로 다른 N개를 일렬로 나열하는 경우의 수입니다. 첫 번째 위치에 N개 선택, 두 번째 위치에 N-1개 선택, 세 번째 위치에 N-2개 선택... 이런 식으로 N × (N-1) × (N-2) × ... × 1 = N!이 되기 때문입니다. 따라서 코딩 테스트에서는 N이 작을 때만 사용해야 합니다.
Q5. 완전 탐색의 단점과 해결 방법은?
답변: 완전 탐색의 단점은 문제의 크기가 커질수록 시간 복잡도가 급격히 증가한다는 것입니다. 이를 해결하기 위해서는 1) 동적 계획법(DP)으로 중복 계산 제거, 2) 그리디 알고리즘으로 최적 선택, 3) 분할 정복으로 문제 분할 등의 최적화 기법을 사용해야 합니다.
📚 원본 참고 자료
출처: 2023-CS-Study
- 링크: algorithm_brute_force_search.md
- 내용: 완전 탐색, 비트마스크, 재귀, 순열, BFS/DFS