Exhaustive search

Exhaustive search(완전 탐색) 알고리즘은 가능한 경우의 수를 모두 확인해서 찾는 방법이다.

방법

• Brute force

  • 반복/조건문을 통해 가능한 모든 방법을 단순히 찾는 경우

• Backtracking

  • recursive를 이용하여 진행하고 만약 정답이 아닐 것 같으면 더 이상 가지 않고 return한다.

• Permutation

• bit mask

  • 2진수를 이용하는 방식
  • 각각의 원소가 포함되거나, 포함되지 않는 경우만 있는 문제에서 주로 사용

• BFS/DFS

  • 단순 경로 문제라면 BFS/DFS만
  • 도로 + 장애물 or 목적지 과 같은 추가적인 작업이 필요한 경우 Exxhaustive search + BFS/DFS사용