완전탐색

• ‘브루트 포스’ 라고도 하며, 컴퓨터의 빠른 계산 능력을 이용하여 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법
• 완전 탐색은 N의 크기가 작을 때 이용이 되기 때문에 보통 시간 복잡도가 지수승이나, 팩토리얼 꼴로 나올 때 많이 이용
  • 입력으로 주어지는 크기가 매우 작음!
• 알고리즘 유형
• 단순 Brute-Force
• 비트마스크(Bitmask)
• 재귀 함수
• 순열 (Permutation)
• BFS / DFS
• 백트래킹

비트마스크

• 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식
• 완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용이 가능
• 원소가 5개인 집합의 모든 부분집합을 구하는 경우
  • 어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않는 두 가지 경우만 존재한다.
  • 따라서 5자리 이진수 (0 ~ 31)를 이용하여 각 원소의 포함 여부를 체크 가능함