완전탐색

1. 완전 탐색

• 모든 경우의 수를 고려하는 탐색 알고리즘

2. 종류

• 브루트 포스: for문을 이용하여 처음부터 끝까지 탐색
  • 데이터의 갯수가 100만개 이하일때 적절
• 비트마스크: 이진수 표현을 자료구조로 쓰는 기법
  • 모든 경우의 수가 각각의 원소에 포함되거나 포함되지 않는 2가지 선택으로 구성되는 경우 용이함.
  • 정수로 집합을 나타낼 수 있음
  • {1,3,4,5,9} = 570 = 2^1+2^3+2^4+2^5+2^9
  • 공간적인 이유+ 정수하나로 배열을 대체할수 있기 때문에
• 백트래킹: 분할 정복을 이용한 기법, 재귀함수를 이용,
  해를 찾아가는 도중에 해가 될것 같지 않은 경로가 있다면 더 이상 가지 않고 되돌아감
• 재귀함수: 함수 내에서 함수 자기 자신을 계속해서 호출하는 것
• 순열: 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수
• BFS/DFS

참고 자료

• 완탐중) 순열과 조합
• 달려라승이 -탐색(bfs,dfs)
• 완전 탐색 (Brute-Force Search / Exhaustive Search) 알고리즘