JAVA_코딩테스트 준비_완전 탐색 알고리즘 (부르트포스 / Brute-Force Algorithm)

완전 탐색 알고리즘 (부르트포스 / Brute-Force Algorithm)

부르트포스 알고리즘은 단순하게 특정 값을 구하기 위해 가능한 값을 처음부터 끝까지 다 넣는것이라고 보면 된다. 

예를들어 자물쇠 번호를 잊어버렸을 때, 자물쇠 버튼을 000~999까지 눌러보면서 맞는 숫자 나올때 까지 돌리는 것과 비슷하다. 

자물쇠 버튼 누르는건 내 손의 빠르기에 달려있는 것 처럼, 부르트 포스 알고리즘은 컴퓨터의 성능에 달려 있다. 

모든 가능성을 시도해서 답을 찾아내는 것이기 때문에 공간복잡도(알고리즘 구현하는데 사용되는 메모리 크기)와 시간 복잡도를 신경쓰지 않는다. 

부르트포스를 쓰는 이유는 앞서 특정한 값을 찾거나 할 때 최악의 경우의 수시행 하더라도 답을 찾기 위해 사용된다.

부르트포스 동작 예시 (출처 : 코드스테이츠)

부르트포스는 크게 두가지 경우에 사용된다.

1. 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
   (직접 일일히 넣는거 말고 답 없을때)
   
   
2. 문제를 해결하는 솔루션이 여러개 있을 때 이 솔루션을 일일히 확인할 때

부르트포스는 하나하나 일일히 값을 넣어보면서 계속 연산을 하는것이므로, 문제의 목잡도에 치명적인 단점이 있다. 

시간복잡도 O(n) , O(log n)은 그나마 나은데, O(n) , O(n^2) , O(2^n) 의 복잡도를 가진 경우, 데이터 범위가 넓어지는 순간부터 연산 시간은 기하급수적으로 늘어난다. 

일반적으로, 내 컴퓨터 자원(메모리, 프로세스 속도)가 커버 가능하면 부르트 포스를 사용해도 된다, 하지만 불가능 할 경우 다른 알고리즘을 채택하여 다소 정확도가 떨어지더라도 효율성을 보장해야 한다.