영상, 글 요약
가장 기본적인 알고리즘, 브루트 포스(Brute Force) : 모든 경우 고려하는 알고리즘
kimbro6
2023. 1. 20. 00:01
#1 들어가기 전
브루트 포스(Brute Force)
brute: 무식한, force: 힘
브루트 포스는 모든 경우를 고려하는 알고리즘이다.
그러므로, 시간을 오래 걸리더라도 100% 정확한 답을 찾을 수 있다.
#2 본론
브루트 포스 알고리즘을 문제에 직접 적용하려면 우선 인풋의 범위와 시간제한을 확인해야 한다.
모든경우를 고려했을때, 예상되는 연산의 수를 계산해 보고 그 연산을 시간제한 안에 완료할 수 있는지 여부를 확인하는 작업이다.
pypy3로 제출 할 경우, 1초에 약 2000만~1억번의 연산이 가능하다.
일반 python3로 제출할 경우, 1초에 약 2000만번의 연산이 가능하다.
또한 c++의 경우, 1초에 약 1억번의 연산이 가능하다고 한다.
예를들어 주어진 배열중에 " 1 " 을 찾는다고가정하자.
시간제한이 1초이고, python3로 제출 한다고 할때, 배열의 길이가 2000만 안쪽이라면 모든 경우를 고려해서 완벽한 답을 낼 수 있다. 하지만 2000만 보다 크다면, 시간초과가 날 확률이 크다.
물론, 이분검색을통해 연산을 더 줄일수도 있다.