가장 기본적인 알고리즘, 브루트 포스(Brute Force) : 모든 경우 고려하는 알고리즘

#1 들어가기 전

브루트 포스(Brute Force)

brute: 무식한, force: 힘

 

브루트 포스는 모든 경우를 고려하는 알고리즘이다.

그러므로, 시간을 오래 걸리더라도 100% 정확한 답을 찾을 수 있다.

 

#2 본론

브루트 포스 알고리즘을 문제에 직접 적용하려면 우선 인풋의 범위와 시간제한을 확인해야 한다.

모든경우를 고려했을때, 예상되는 연산의 수를 계산해 보고 그 연산을 시간제한 안에 완료할 수 있는지 여부를 확인하는 작업이다.

 

pypy3로 제출 할 경우, 1초에 약 2000만~1억번의 연산이 가능하다.

일반 python3로 제출할 경우, 1초에 약 2000만번의 연산이 가능하다.

또한 c++의 경우, 1초에 약 1억번의 연산이 가능하다고 한다.

 

예를들어 주어진 배열중에 " 1 " 을 찾는다고가정하자.

시간제한이 1초이고, python3로 제출 한다고 할때, 배열의 길이가 2000만 안쪽이라면 모든 경우를 고려해서 완벽한 답을 낼 수 있다. 하지만 2000만 보다 크다면, 시간초과가 날 확률이 크다.

물론, 이분검색을통해 연산을 더 줄일수도 있다.

#4 참고자료

https://hcr3066.tistory.com/26