완전 검색, 완전 탐색(Exhaustive Search)

완전 검색?

완전 검색은 이름 그대로 모든 경우의 수를 체크하는 기법이다.

 

Brute force 혹은 Generate and test 기법이라고도 한다.

여기서 force는 사람(지능)보다는 컴퓨터의 force를 의미한다.

 

모든 경우의 수를 테스트한 후, 최종 해법을 도출하기 때문에, 수행 속도는 느리지만, 해답을 찾지 못할 확률은 적다.

---

언제 사용하는가?

상대적으로 빠른 시간에 문제를 해결(알고리즘 설계)할 수 있기 때문에, 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.

 

예를 들어 N개의 숫자로 N자리 수를 만들 수 있는 모든 경우의 수는 N!개인데, 10!의 경우 약 360만, 11!은 약 4000만, 12!은 약 4억8천만이다.

Java를 사용할 때 대략적으로 1억번 연산에 1초 조금 안된다고 생각하면 되므로, 웬만한 문제에서는 11!을 넘기지 않는것이 좋을 것 같다.

 

문제를 풀 때, 완전 검색으로 접근해서 답을 낸 후 다른 알고리즘을 통해 성능개선을 시도하는 것이 바람직하다.

---

마무리

전형적으로 순열(Permutation), 조합(Combination), 부분집합(Subset)과 같은 조합적 문제들과 연관된다.

 

따라서 다음 포스팅부터 순열, 조합, 부분집합의 개념을 정리하려고 한다.