무차별 대입 검색
컴퓨터 과학에서 생성 및 테스트라고도 알려진 무차별 대입 검색(brute-force search) 또는 완전 검색(exhaustive search)은 각 후보가 문제의 설명을 만족하는지 여부에 대해 가능한 모든 후보를 체계적으로 확인하는 것으로 구성된 매우 일반적인 문제 해결 기술 및 알고리즘 패러다임이다.
자연수 n의 제수를 찾는 무차별 대입 알고리즘은 1부터 n까지의 모든 정수를 열거하고 각각이 n을 나머지 없이 나누는지 확인한다. 여덟 퀸 문제에 대한 무차별 접근 방식은 64제곱 체스판에서 8개 조각의 가능한 모든 배열을 검사하고 각 배열에 대해 각(퀸) 조각이 다른 조각을 공격할 수 있는지 확인한다.[1]
무차별 대입 검색은 구현하기 간단하고 솔루션이 존재하는 경우 항상 솔루션을 찾는 반면, 구현 비용은 후보 솔루션의 수에 비례한다. 많은 실제 문제에서 문제의 규모가 커짐에 따라 매우 빠르게 증가하는 경향이 있다.[2] 따라서 무차별 대입 검색은 일반적으로 문제 크기가 제한되어 있거나 후보 솔루션 세트를 관리 가능한 크기로 줄이는 데 사용할 수 있는 문제별 휴리스틱이 있는 경우에 사용된다. 이 방법은 처리 속도보다 구현의 단순성이 더 중요한 경우에도 사용된다.
예를 들어, 알고리즘의 오차가 매우 심각한 결과를 초래할 수 있는 중요한 응용 프로그램이나 컴퓨터를 사용하여 수학적 정리를 증명하는 경우가 이에 해당한다. 무차별 검색은 다른 알고리즘이나 메타 휴리스틱을 벤치마킹할 때 기본 방법으로도 유용하다. 실제로 무차별 대입 검색은 가장 간단한 메타휴리스틱으로 볼 수 있다. 무차별 대입 검색은 퇴각검색과는 구별된다. 여기서는 명시적으로 열거되지 않고 대규모 솔루션 세트를 삭제할 수 있다(위의 여덟 퀸 문제에 대한 교과서 컴퓨터 솔루션에서와 같이). 테이블에서 항목을 찾는 무차별 대입 방법, 즉 후자의 모든 항목을 순차적으로 확인하는 방법을 선형 검색이라고 한다.
같이 보기
편집각주
편집- ↑ “Brute Force Algorithms Explained”. 《freeCodeCamp.org》 (영어). 2020년 1월 6일. 2021년 4월 11일에 확인함.
- ↑ “Complexity of brute force search”. 《coursera》. 2018년 6월 14일에 확인함.