브루트-포스 알고리즘

1. 완전탐색 알고리즘

• 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.
• 이 알고리즘의 강력한 점은 예외 없이 100% 확률로 정답만을 출력한다. BUT 그만큼 높은 시간 복잡도를 갖는다.
• 너비 우선 탐색(BFS)와 관련이 깊다.

 

🌟 완전 탐색 알고리즘과의 차이점

• 완전 탐색 알고리즘 : 모든 경우의 수를 전부 탐색하는 알고리즘, 그 결과를 찾는 것보다 탐색한다는 과정에 중점
• 브루트포스 알고리즘 : 문제를 해결하기 위해, 모든 경우를 탐색하고 답을 도출하는 알고리즘, 결과를 찾는 것에 중점

 

2. 문제 해결 방법

1. 주어진 문제를 선형 구조로 구조화한다.
2. 구조화된 문제 공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
3. 구성된 해를 정리한다.

 

3. 사용 조건 및 예제

• 문제에서 달성하고자 하는 솔루션이 잘 정의되어 있어야 한다.
  • 솔루션이 잘 정의되어 있지 않으면, 브루트 포스를 사용한  솔루션이 올바른지의 여부를 확인할 수 없다.
• 문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.
  • 문제에서 고려해야 할 솔루션의 수가 한정되어야 한다. 너무 많으면 브루트 포스 알고리즘은 효율적이지 않은 방법이다.

1. 10의 약수의 합 구하기
2. 거스름돈을 지불할 수 있는 방법의 수와 최소 동전의 개수 구하기
3. 반복문/조건문 or 재귀를 사용하는 모든 경우

---

자료 참고

https://olrlobt.tistory.com/33

https://hcr3066.tistory.com/26