Brute Force

Brute Force는 솔루션에 대해 가능한 모든 후보를 체계적으로 열거하고 각 후보가 문제의 조건을 충족하는지 확인 하는 매우 일반적인 문제 해결 기술 및 알고리즘 패러다임이다.

Brute Force 알고리즘이란 Exhaustive Search, 완전탐색이라고도 하며 가능한 모든 경우의 수를 체크하여 정답을 찾는 방법이다. 경우의 수가 많아질수록 정답을 찾는데 걸리는 시간은 증가하지만 어떠한 경우라도 항상 정답을 보장 한다는 장점이 있다.

Brute Force의 장단점

• 장점
  • 알고리즘의 설계와 구현이 매우 간단하다
  • 항상 정답을 보장한다
• 단점
  • 시간복잡도가 매우 높다
  • 공간복잡도가 매우 높다

Brute Force의 종류

• 선형 구조 : 순차 탐색
• 비 선형 구조 : DFS/BFS, Backtracking

완전탐색의 종류

• Brute Force : 조건문과 반복문을 통해 모든 경우의 수를 탐색
• Bit Mask : 2진수 연산을 통해 경우의 수를 탐색하는 방법
  • 선택지가 2개(포함되거나 포함되지 않거나)일때 유용
• Permutation : 순열
• Recursive : 재귀
  • 탈출조건 필요
  • 현재 함수의 상태를 저장하는 parameter필요
• BFS/DFS : 그래프의 모든 노드를 탐색하는 방법
• Backtracking : DFS에서 정답 가능성이 없는 노드를 방문하지 않아 경우의 수를 줄이는 방법