[알고리즘] 완전 탐색 알고리즘(Brute-Force Algorithm, BFA)

 컴퓨터 과학에서 Brute Force는 시행착오 방법론을 말한다. 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 모두 나열하면서 답을 찾는 방법이다.

 

 이 방법은 직관적이어서 이해하기 쉬우며 문제의 정확한 답을 얻어낼 수 있는 가장 확실하고 기초적인 방법이다.

 

 예를 들어, 4개의 숫자로 구성된 자물쇠를 푼다고 하면 0000부터 9999까지 모두 시도해 보면 해결할 수 있다. 이렇게 하나하나 대입하여 시도하는 방식 완전 탐색 알고리즘이라고 한다.

 

 완전 탐색 알고리즘은 공간 복잡도와 시간 복잡도의 요소를 고려하지 않고 솔루션을 찾으려고 하는 방법이기 때문에 최적의 솔루션은 아닐 수 있다.

 

 

 

 

 사용

 완전 탐색 알고리즘은 크게 다음과 같은 두 가지 경우에 사용한다.

 

• 프로세스 속도를 높이는 데 사용할 수 있는 다른 알고리즘이 없을 때
  
  
• 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

 

 보통 완전 탐색 알고리즘은 문제에 더 적절한 해결 방법을 찾기 전에 시도하는 방법이다. 하지만 데이터의 범위가 커질수록 상당히 비효율적이므로, 프로젝트의 규모가 커진다면 더 효율적인 알고리즘을 사용해야 할 것이다.

 

 

 

 

한계

 완전 탐색 알고리즘은 문제의 복잡도에 매우 민감하다는 단점을 가지고 있다.

 

 문제가 복잡해질수록 시간이나 컴퓨팅 자원 등 많은 자원의 필요량이 기하급수적으로 증가하기 때문에 비효율적인 알고리즘이 될 수 있다.

 

 일반적으로 문제의 규모가 현재 자원으로 충분히 커버가 가능한 경우에는 사용하지만, 이를 벗어난 경우에는 정확도를 조금 희생하더라도 더 효율적인 알고리즘을 사용한다.