Brute Force (브루트 포스) 알고리즘

개념

브루트 포스를 사전적 의미로 찾아본다면 아래와 같다.
브루트(Brute) : 무식한     +     포스(Force) : 힘
즉, 발생할 수 있는 모든 경우를 무식하게 탐색한다는 뜻이다. 전체를 탐색한다는 의미에서 전체 탐색, 완전 탐색이라고도 한다.
브루트 포스 알고리즘을 설계할 때는 해가 하나 이상 존재한다는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

장단점

장점)

 

알고리즘을 설계하고 구현하기 매우 쉽다.

복잡한 알고리즘 없이 빠르게 구현할 수 있다.

 

단점)

 

알고리즘의 실행 시간이 매우 오래 걸린다.

메모리 효율면에서 매우 비효율적이다.

종류

선형 구조) 순차 탐색

비선형 구조) 백트래킹, dfs, bfs

예시

만약 10자리 비밀번호 자물쇠가 있다고 가정해보자.
이 자물쇠를 풀기 위해서 브루트 포스 방식을 적용한다면  0000000000에서 9999999999까지 모든 수를 대입해서 풀어야 할 것이다. 아무리 요즘 컴퓨터의 성능이 좋다 하더라도 짧은 시간 안에 이것을 해결하기는 무리가 있다.

또 다른 브루트 포스 예시를 들어보자.
1부터 100억까지의 합을 브루트 포스로 구한다고 하면 반복문으로 1부터 100억까지 증가시키면서 total 변수에 누적시켜야 할 것이다. 등차수열의 합 공식을 사용한다면 쉽게 해결할 수 있는 문제이기 때문에 이것을 브루트 포스로 해결한다면 시간적, 메모리적으로 매우 비효율적인 해결 방법이 된다.

 

 

출처