무차별 대입 검색

컴퓨터 과학에서 생성 및 테스트라고도 알려진 무차별 대입 검색(brute-force search) 또는 완전 검색(exhaustive search)은 각 후보가 문제의 설명을 만족하는지 여부에 대해 가능한 모든 후보를 체계적으로 확인하는 것으로 구성된 매우 일반적인 문제 해결 기술 및 알고리즘 패러다임이다.

자연수 n의 제수를 찾는 무차별 대입 알고리즘은 1부터 n까지의 모든 정수를 열거하고 각각이 n을 나머지 없이 나누는지 확인한다. 여덟 퀸 문제에 대한 무차별 접근 방식은 64제곱 체스판에서 8개 조각의 가능한 모든 배열을 검사하고 각 배열에 대해 각(퀸) 조각이 다른 조각을 공격할 수 있는지 확인한다.

무차별 대입 검색은 구현하기 간단하고 솔루션이 존재하는 경우 항상 솔루션을 찾는 반면, 구현 비용은 후보 솔루션의 수에 비례한다. 많은 실제 문제에서 문제의 규모가 커짐에 따라 매우 빠르게 증가하는 경향이 있다. 따라서 무차별 대입 검색은 일반적으로 문제 크기가 제한되어 있거나 후보 솔루션 세트를 관리 가능한 크기로 줄이는 데 사용할 수 있는 문제별 휴리스틱이 있는 경우에 사용된다. 이 방법은 처리 속도보다 구현의 단순성이 더 중요한 경우에도 사용된다.

예를 들어, 알고리즘의 오차가 매우 심각한 결과를 초래할 수 있는 중요한 응용 프로그램이나 컴퓨터를 사용하여 수학적 정리를 증명하는 경우가 이에 해당한다. 무차별 검색은 다른 알고리즘이나 메타 휴리스틱을 벤치마킹할 때 기본 방법으로도 유용하다. 실제로 무차별 대입 검색은 가장 간단한 메타휴리스틱으로 볼 수 있다. 무차별 대입 검색은 퇴각검색과는 구별된다. 여기서는 명시적으로 열거되지 않고 대규모 솔루션 세트를 삭제할 수 있다(위의 여덟 퀸 문제에 대한 교과서 컴퓨터 솔루션에서와 같이). 테이블에서 항목을 찾는 무차별 대입 방법, 즉 후자의 모든 항목을 순차적으로 확인하는 방법을 선형 검색이라고 한다.

무차별 대입 검색 구현

기본 알고리즘
특정 문제 부류에 무차별 대입 검색을 적용하기 위해서는 first, next, valid, output의 네 가지 서브루틴을 구현해야 한다. 이 절차들은 해결할 문제의 특정 인스턴스에 대한 데이터 P를 매개변수로 받아야 하며, 다음을 수행해야 한다.
 first (P): P에 대한 첫 번째 후보 해법을 생성한다.
 next (P, c): 현재 후보 c 이후 P에 대한 다음 후보를 생성한다.
 valid (P, c): 후보 c가 P에 대한 해법인지 확인한다.
 output (P, c): P의 해법 c를 해당 애플리케이션에 맞게 사용한다.
next 절차는 또한 현재 후보 c 이후 P 인스턴스에 더 이상 후보가 없을 때를 알려야 한다. 이를 수행하는 편리한 방법은 "널 후보", 즉 실제 후보와 다른 몇 가지 관습적인 데이터 값 Λ를 반환하는 것이다. 마찬가지로 first 절차는 P 인스턴스에 후보가 전혀 없을 경우 Λ를 반환해야 한다. 무차별 대입 방법은 다음과 같은 알고리즘으로 표현된다.
 c ← first(P)
 while c ≠ Λ do
     if valid(P,c) then
         output(P, c)
     c ← next(P, c)
 end while
예를 들어, 정수 n의 약수를 찾을 때, 인스턴스 데이터 P는 숫자 n이다. first(n) 호출은 n ≥ 1이면 정수 1을 반환하고, 그렇지 않으면 Λ를 반환해야 한다. next(n,c) 호출은 c < n이면 c + 1을 반환하고, 그렇지 않으면 Λ를 반환해야 한다. 그리고 valid(n,c)는 c가 n의 약수인 경우에만 참을 반환해야 한다. (사실, Λ를 n + 1로 선택하면 n ≥ 1 및 c < n 테스트는 불필요하다.) 위 무차별 대입 검색 알고리즘은 주어진 인스턴스 P의 해법인 모든 후보에 대해 output을 호출한다. 이 알고리즘은 첫 번째 해법 또는 지정된 수의 해법을 찾은 후 중단하도록 쉽게 수정될 수 있다. 또는 지정된 수의 후보를 테스트한 후, 또는 주어진 양의 CPU 시간을 보낸 후 중단하도록 수정할 수도 있다.

조합 폭발
무차별 대입 방법의 주요 단점은 많은 실제 문제에서 자연 후보의 수가 엄청나게 많다는 것이다. 예를 들어, 위에서 설명한 대로 숫자의 약수를 찾을 때 테스트되는 후보의 수는 주어진 숫자 n이 될 것이다. 따라서 n이 16진수 자리라면 검색은 적어도 1015개의 컴퓨터 명령을 실행해야 하며, 이는 일반적인 PC에서 며칠이 걸릴 것이다. n이 무작위 64-비트 자연수이고 평균적으로 약 19진수 자리인 경우 검색은 약 10년이 걸릴 것이다. 데이터 크기가 증가함에 따라 후보 수가 급격히 증가하는 이 현상은 모든 종류의 문제에서 발생한다. 예를 들어, 10개의 문자를 특정 순서로 재배열하는 것을 찾고 있다면 10! = 3,628,800개의 후보를 고려해야 하며, 이는 일반적인 PC에서 1초 이내에 생성하고 테스트할 수 있다. 그러나 하나의 문자를 더 추가하는 것이는 데이터 크기의 10% 증가에 불과하다은 후보 수를 11배, 즉 1000% 증가시킨다. 20개의 문자일 경우 후보 수는 20!이며, 이는 약 2.4×1018 또는 2.4 경에 해당하며, 검색은 약 10년이 걸릴 것이다. 이 반갑지 않은 현상을 흔히 조합 폭발 또는 차원의 저주라고 부른다.

조합 복잡성으로 인해 풀이 가능성 한계가 발생하는 한 가지 예는 체스 풀기이다. 체스는 풀린 게임이 아니다. 2005년에는 여섯 개 이하의 말로 끝나는 모든 체스 게임 엔딩이 해결되어, 완벽하게 플레이할 경우 각 포지션의 결과를 보여주었다. 하나의 체스 말을 더 추가하여 테이블베이스를 완성하는 데 10년이 더 걸렸고, 7개의 말을 포함하는 테이블베이스가 완성되었다. 체스 엔딩에 하나의 말을 더 추가하는 것(따라서 8개의 말을 포함하는 테이블베이스를 만드는 것)은 추가된 조합 복잡성으로 인해 다루기 어렵다고 간주된다.

무차별 대입 검색 속도 향상
무차별 대입 알고리즘의 속도를 높이는 한 가지 방법은 문제 클래스에 특정한 휴리스틱을 사용하여 검색 공간, 즉 후보 해법 집합을 줄이는 것이다. 예를 들어, 여덟 퀸 문제에서는 여덟 퀸을 표준 체스판에 놓아 어떤 퀸도 다른 퀸을 공격하지 않도록 하는 것이 과제이다. 각 퀸은 64개의 사각형 중 어느 곳에나 놓일 수 있으므로, 원칙적으로 고려해야 할 경우의 수는 648 = 281,474,976,710,656가지이다. 그러나 퀸들은 모두 같고, 두 퀸이 같은 사각형에 놓일 수 없으므로, 후보는 64개 사각형 집합에서 8개의 사각형을 선택하는 모든 가능한 방법이다. 즉, 64C8 = 64!/(56!*8!) = 4,426,165,368개의 후보 해법이다이전 추정치의 약 1/60,000이다. 또한, 두 퀸이 같은 행이나 같은 열에 있는 배열은 해법이 될 수 없다. 따라서 후보 집합을 해당 배열로 더 제한할 수 있다.

이 예시가 보여주듯이, 약간의 분석만으로도 후보 해법의 수를 극적으로 줄일 수 있으며, 다루기 어려운 문제를 사소한 문제로 바꿀 수 있다.

경우에 따라 분석을 통해 후보를 모든 유효한 해법 집합으로 줄일 수도 있다. 즉, 테스트와 유효하지 않은 후보 생성을 낭비하지 않고 모든 원하는 해법을 직접 열거하는 알고리즘(또는 적절한 경우 하나의 해법을 찾는 알고리즘)을 제공할 수 있다. 예를 들어, "1에서 1,000,000 사이의 정수 중 417로 균등하게 나누어지는 모든 정수를 찾으라"는 문제의 경우, 순진한 무차별 대입 해법은 범위 내의 모든 정수를 생성하고 각각의 나누어떨어짐 여부를 테스트할 것이다. 그러나 이 문제는 417에서 시작하여 숫자가 1,000,000을 초과할 때까지 417을 반복적으로 더함으로써 훨씬 더 효율적으로 해결할 수 있다이는 2398(= 1,000,000 ÷ 417) 단계만 필요하며 테스트는 필요 없다.

검색 공간 재정렬
모든 해법이 아니라 하나의 해법만 필요한 애플리케이션에서 무차별 대입 검색의 기대 실행 시간은 후보가 테스트되는 순서에 따라 달라지는 경우가 많다. 일반적인 규칙으로 가장 유망한 후보를 먼저 테스트해야 한다. 예를 들어, 무작위 숫자 n의 적절한 약수를 검색할 때, 후보 약수를 2부터 까지 증가하는 순서로 열거하는 것이 다른 방법보다 낫다n이 c로 나누어떨어질 확률은 1/c이기 때문이다. 더욱이 후보가 유효할 확률은 이전의 실패한 시도에 의해 종종 영향을 받는다. 예를 들어, 주어진 1000비트 문자열 P에서 1 비트를 찾는 문제를 고려해 보자. 이 경우 후보 해법은 인덱스 1부터 1000까지이며, P[c] = 1일 때 후보 c가 유효하다. 이제 P의 첫 번째 비트가 0 또는 1일 확률이 같지만, 그 이후의 각 비트는 이전 비트와 90% 확률로 같다고 가정해 보자. 후보가 1부터 1000까지 증가하는 순서로 열거되면 성공하기 전에 검사되는 후보의 수 t는 평균적으로 약 6개가 될 것이다. 반면에 후보가 1,11,21,31...991,2,12,22,32 등의 순서로 열거되면 t의 기대값은 2보다 약간 많을 뿐이다. 일반적으로 검색 공간은 이전 시도가 유효하지 않았을 때 다음 후보가 유효할 가능성이 가장 높은 방식으로 열거되어야 한다. 따라서 유효한 해법이 어떤 의미에서 "클러스터링"될 가능성이 있다면, 각 새로운 후보는 동일한 의미에서 이전 후보들과 가능한 한 멀리 떨어져 있어야 한다. 물론 해법이 우연히 예상되는 것보다 더 균일하게 퍼져 있을 가능성이 있다면 그 반대가 적용된다.

무차별 대입 검색의 대안
해법에 대해 가질 수 있는 다양한 종류의 부분 지식을 활용하도록 설계된 다른 많은 검색 방법 또는 메타휴리스틱이 있다. 휴리스틱을 사용하여 검색의 일부를 조기에 차단할 수도 있다. 이에 대한 한 가지 예는 게임 트리를 검색하는 최소극대화 원리로, 검색 초기 단계에서 많은 서브트리를 제거한다. 언어 구문 분석과 같은 특정 분야에서는 차트 파싱과 같은 기술을 사용하여 문제의 제약 조건을 활용하여 지수 복잡성 문제를 다항 복잡성 문제로 줄일 수 있다. 제약 만족 문제와 같은 많은 경우에 제약 전파를 통해 검색 공간을 극적으로 줄일 수 있으며, 이는 제약 프로그래밍 언어에서 효율적으로 구현된다. 문제에 대한 검색 공간은 전체 문제를 단순화된 버전으로 대체하여 줄일 수도 있다. 예를 들어, 컴퓨터 체스에서는 게임의 나머지 부분에 대한 모든 가능한 움직임의 완전한 최소극대화 트리를 계산하는 대신, 특정 수의 움직임에서 가지치기하고 나머지 트리는 정적 평가 함수로 근사하는 보다 제한된 최소극대화 가능성 트리가 계산된다.

암호학에서

암호학에서 무차별 대입 공격은 올바른 키를 찾을 때까지 가능한 모든 키를 체계적으로 확인하는 것을 포함한다.Mark Burnett, "Blocking Brute Force Attacks" , UVA Computer Science, 2007 이 전략은 이론적으로 어떤 암호화된 데이터에도 사용될 수 있다 (원 타임 패드 제외). 공격자는 암호화 시스템의 약점을 이용할 수 없어 자신의 작업을 더 쉽게 만들 수 없는 경우에 이 전략을 사용한다.

암호화에 사용되는 키 길이는 무차별 대입 공격을 수행할 수 있는 실용적인 가능성을 결정하며, 긴 키는 짧은 키보다 해독하기가 기하급수적으로 더 어렵다. 무차별 대입 공격은 인코딩될 데이터를 난독화하여 효율성을 떨어뜨릴 수 있는데, 이는 공격자가 코드를 해독했을 때 이를 인식하기 어렵게 만든다. 암호화 시스템의 강도를 측정하는 척도 중 하나는 공격자가 성공적인 무차별 대입 공격을 수행하는 데 이론적으로 얼마나 오래 걸리는지이다.

 같이 보기 
 무차별 대입 공격
 점근 표기법
 반복문#컴퓨팅

 각주 

분류:검색 알고리즘