♟ 단순/강력, 모든 경우의 수를 살펴보는 완전탐색(Brute-force)

관련글 :

그리디	https://waydd.tistory.com/91
DP	https://waydd.tistory.com/92
모든 조합, 순열 구하기	https://waydd.tistory.com/108
백트래킹 문제	https://waydd.tistory.com/107

 

 

1. 완전 탐색

 

모든 경우의 수를 하나씩 전부 탐색하여 문제의 해답을 찾는 알고리즘

• 모든 경우의 수를 시도, 최적해를 반드시 구할 수 있음
• 로직이 복합하지 않아 구현이 쉬움 (단순, 직관적)
• 일반적으로 시간 복잡도는 경우의 수에 따라 O(N!), O(2^N), O(N^2) 등 매우 큼, 작은 입력에만 적합
  → 입력 크기가 커질수록 연산 시간이 급격히 증가
  → 실전에서 제한시간 초과(TLE) 자주 발생 (= 한계)
  → 대안으로 백트래킹(가지치기) 혹은 그리디, DP, 이분 탐색, DFS/BFS 로 최적화
• 순열(카드 문제), 조합(로또 번호 선택), 부분집합(최대 부분합) 등을 구하는데 사용되거나, 백트래킹 문제( N-Queen, 스도쿠 ) 에 사용

 

- 활용 예시

•  전체 경우의 수를 고려해야 하나? (모든 경우 탐색)이 적합할 때 사용
• 거스름돈 문제
  → 500원을 안 쓰는 경우도 다 계산, 모든 조합을 시도하여 가장 적은 개수를 찾음
  → 이 문제는 그리디가 항상 최적의 해를 줌, 완전탐색보다는 그리디 사용
• 비선형 문제
  → 모든 경로를 다 탐색해서 최고 점수의 경로를 찾음
  → 그리디가 정답을 보장하지 않음

 

- 알고리즘 간 전략 연관성

• TSP (외판원 문제) : 모든 경로 탐색 → Bitmask DP 로 최적화 가능 (브루트포스 → DP 진화 대표 예)
• 백트래킹 (N-Queen 등) : 완전탐색(모든 위치 시도) + 백트래킹(가지치기)
  → 조건에 맞는 모든 경우의 수를 재귀 탐색  (비트마스크 사용 시 DP적 성격)
• 순열 / 조합 생성 : itertools.permutations, DFS로 직접 구현 등
• Knapsack (DFS 방식) : 순수 DFS, 모든 조합 탐색 (최악 O(2^N))
• Bitmask DP : DP + 완전탐색

 

 

2. 문제 해결 사고 흐름

 

- 단계별 설명

	설명	핵심	예시
1. 문제 요구 조건 분석	가능한 모든 경우를 직접 시도해야 하는지 판단	경우의 수가 크지 않은가? 모든 조합/순열을 검사해야 하는가?	- 9명 중 7명 고르기 (백준 2309) - 모든 경로 탐색 문제
2. 가능한 모든 경우의 수 정의	무엇을 바꿔가며 시도할지 결정	조합? 순열? 중복 허용? 순서 상관? 등을 명확히 구분	- itertools.permutations, combinations 등 사용 가능
3. 반복/재귀/백트래킹 구조 설계	문제에 맞는 탐색 구조를 선택하여 구현	반복문, 재귀, DFS/BFS, 백트래킹 등으로 모든 경우 탐색	- for-loop 2~3중첩 - 재귀함수 사용 - DFS로 모든 경로 탐색
4. 조건 검증 및 정답 업데이트	탐색 중 조건을 만족하는 경우만 정답으로 고려	조건문으로 필터링 최솟값/최댓값 갱신	- if 조건 만족하면 min = min(min, 값) 등
5. 시간 복잡도 체크	가능한 경우의 수가 수행 시간 안에 가능한가?	N!이면 N≤10, 2^N이면 N≤20 정도까지 초당 1억 연산 기준으로 추산	- 8명 순열 → 8! = 40,320 (가능) - 25명 순열 → 25! (불가능)

 

- 자주 사용하는 완전 탐색 구현 도구

	도구	예시
순열	itertools.permutations(iter, r)	좌석 배치, 숫자 카드 나열
조합	itertools.combinations(iter, r)	팀 나누기, 7난쟁이
중복 순열	product(iter, repeat=r)	자릿수 조합, 게임 경우의 수
DFS 재귀	def dfs(idx): ...	미로 탐색, 문자열 조합 등
BFS 큐	queue = deque([...])	최단 거리 탐색, 퍼지는 전염 등