완전탐색

완전탐색이란?

• 모든 경우의 수를 다 체크해서 정답을 찾는 방법론

• 수도 코드

c ←first(P)
while c ≠ Λ do
	if valid(P,c)
		then output(P,c)
	c ←next(P,c)
end while

→ P의 solution 후보 c를 모두 검사하는 과정

• 알고리즘 자체는 아니기에 완전 탐색을 위해 여러 알고리즘 기법을 사용
  • 단순 Brute-Force
  • 비트마스크(2진수 표현 기법을 활용하는 방법)
  • 재귀
  • 순열
  • BFS/DFS

완전 탐색을 위한 알고리즘 기법

1. 단순 Brute-Force

   • 단순 반복/조건문을 통해 모든 방법을 찾는 경우
   • 시간복잡도는 반복문의 수에 따라 결정

2. 비트마스크

   • 비트 연산을 통해서 부분 집합을 표현하는 방법을 의미
   • 비트 연산 활용법(정수 집합을 비트 연산을 통해 검사할 때)
     • 집합 포함 여부 검사(and 연산)
     • 숫자 추가(or 연산)
     • 특정 숫자 제거(not 과 and 연산)
     • 토글 연산(xor 연산)
     • 전체집합, 공집합 표현(shift 연산)

3. 재귀

   • 자기 자신을 호출
   • 대표적인 예시: 피보나치 수열

   Fibo(n)
   Begin
     if n <= 1 then
          Return n;
     else
          Return Call Fibo(n-1) + Call Fibo(n-2);
     endif
   End

   • 조건
     1. 탈출 조건 필요
     2. 현재 함수 상태 저장하는 parameter 필요(탈출 조건 위해)
   • 메모이제이션을 통해 시간복잡도 O(N)

4. 순열

   • 완전 탐색의 대표적인 유형
   • 순열을 구하기 위해서 시간복잡도는 O(N!)

5. BFS/DFS

   • BFS는 너비 우선 탐색으로 현재 정점과 인접한 정점을 우선으로 탐색하는 방식
   • DFS는 깊이 우선 탐색으로 현재 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색하는 방식

완전 탐색 실전 이용 예시

1. 데이터의 크기가 작을 경우

2. 답의 범위가 작고, 역추적 가능한 경우

   • 예시)

   Problem - 1395C - Codeforces

위 문제는 1≤n,m≤200의 n개의 정수와 m개의 정수가 주어질 때

0≤an≤2^9, 0≤bm≤2^9, ci=an&bm의 최솟값을 구하는 문제이다.

위 경우에는 n,m을 모두 찾는 과정이 아니라(할 경우에는 200^200 경우의 수, 불가)

cn의 범위가 512 이하이기 떄문에 c1|c2|...|cn 또한 512 이하이다.

이 경우는 답을 완전탐색하는 경우이다.

참고

https://hongjw1938.tistory.com/78

https://rebro.kr/59

https://www.freecodecamp.org/news/brute-force-algorithms-explained/

https://en.wikipedia.org/wiki/Brute-force_search