[알고리즘] 브루트 포스(brute force)

브루트 포스 (brute force)

• Brute : 무식한 + Force : 힘 = 무식한 힘
• 완전탐색 알고리즘
• 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져옴
• 브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있음
  • 어떤 방식으로든 전체 탐색으로 문제를 해결한다면 브루트 포스 알고리즘으로 풀었다고 할 수 있음
• 선형 구조를 전체적으로 탐색하는 순차탐색,
• 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 기본적인 도구

장점

• 알고리즘을 설계하고 구현하기 매우 쉬움
• 복잡한 알고리즘 없이 빠르게 구현 가능

단점

• 알고리즘의 실행 시간이 매우 오래 걸림
• 메모리 효율면에서 매우 비효율적

---

문제 해결 방법

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

브루트포스 예시

만약 10자리 비밀번호 자물쇠가 있다고 가정

브루트 포스 방식을 적용한다면 0000000000 ~ 9999999999 까지 모든 수를 대입해서 푼다

 

예제

1436. 영화감독 숌

https://github.com/yeeun426/algorithmStudy/tree/main/%EB%B0%B1%EC%A4%80/Silver/2839.%E2%80%85%EC%84%A4%ED%83%95%E2%80%85%EB%B0%B0%EB%8B%AC

GitHub - yeeun426/algorithmStudy

2839. 설탕 배달

https://github.com/yeeun426/algorithmStudy/tree/main/%EB%B0%B1%EC%A4%80/Silver/1436.%E2%80%85%EC%98%81%ED%99%94%EA%B0%90%EB%8F%85%E2%80%85%EC%88%8C

GitHub - yeeun426/algorithmStudy