[Algorithm] 완전 탐색, 브루트포스 알고리즘 (Brute Force)

 

[Algorithm] 완전 탐색, 브루트포스 알고리즘 (Brute Force)

완전 탐색, 브루트포스 알고리즘은 이름 그대로 모든 경우를 탐색하여 답을 도출하는 알고리즘입니다.

 

이러한 특징 때문에 정답을 당연히 찾아 맞출수는 있지만, 모든 경우를 탐색하는 만큼 정답이 도출될 때 까지의 시간은 장담할 수 없는 큰 단점이 있습니다. 즉, 시간 복잡도가 매우 큽니다. 즉, 만약 123456789라는 정답이 있을 경우 아래와 같이 동작하게 되는 알고리즘 입니다.

1. 숫자 1 탐색
2. 숫자 2 탐색
3. 숫자 3 탐색
4. ....
5. 숫자 123456787 탐색
6. 숫자 123456788 탐색
7. 숫자 123456789 탐색 후 정답 도출

 

이러한 특징으로 인해 브루트포스 알고리즘의 경우 대부분 무한 루프, 중첩되는 for문과 if문을 조합하여 사용하게 됩니다. (모든 경우의 수를 찾아 확인하고, if문으로 정답을 걸러낸 후 break하는 방식)

 

브루트포스를 활용한 코딩 테스트 문제 : https://nirsa.tistory.com/394

 

장점

• 복잡한 알고리즘을 사용하지 않아 빠르게 구현하고, 설계하기가 쉬움
• 모든 경우의 수를 찾아 정답을 도출하기 때문에 결국에는 정답을 찾게 됨

 

단점

• 시간 복잡도가 높아 정답을 도출하기 까지의 시간이 매우 오래 걸림
• 모든 경우의 수를 찾기 때문에 효율적이지 않음