[알고리즘] 브루트 포스 알고리즘

브루트 포스 알고리즘

• 모든 경우를 살펴보는 알고리즘
• 100% 정답을 도출해내지만 수행시간이 오래걸림

 

브루트 포스 알고리즘 사용 가능한 경우 ⭕️

• 조건 수가 작은 경우(시간 초과가 나지 않을 정도로)

 

브루트 포스 알고리즘 사용 불가한 경우 ❌

• 조건으로 걸린 수의 크기가 너무 큰 경우 (예: 1,000,000 이하의 자연수의 소수 개수 출력)
  • 𝑶(𝑵²) 풀이를 사용하면 약 1조 번의 연산이 필요하므로 시간 초과가 남
  • 대응: 여러 수에 대한 소수를 판별해야 하는 경우, 에라토스테네스의 체 알고리즘 이용
    

에라토스테네스의 체 알고리즘: 𝑶(𝑵 𝑙𝑜𝑔(𝑙𝑜𝑔𝑵)

• 최악의 경우인 𝑵 = 1,000,000 인 경우에도 약 500만 번의 연산 내에 문제 해결 가능

 

실제 문제에서 브루트 포스 적용

• 대부분의 문제에서 사용 가능하기 때문에 상황을 정의 하긴 어려움
• 따라서 문제를 보고 브루트 포스적 풀이가 가능한지 파악해야 함
  • 모든 경우의 수를 쉽게 살펴볼 수 있는 구조인가 파악
  • 모든 경우의 수를 살펴 보는 풀이가 시간 초과가 나지 않는지 파악
    

• 브루트 포스적으로 풀면 시간 초과가 나는 경우!
  • 그리디, DP, 수학 과 관련된 문제일 가능성이 높음