[Algorithm 이론] Exhaustive Search (a.k.a., Brute-force / Generate-and-Test) 정리

Exhaustive Search(a.k.a., Brute-force, Generate-and-Test)에 대해 정리하고, Permutations 의 역할에 대해 이해한다.

Exhaustive Search

Exhaustive Search(완전검색)

“문제의 해법(solution)으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법”

즉, 발생할 수 있는 모든 경우의 수(case)를 나열하고, 일련의 방법으로 정답을 탐색하는 기법

(a.k.a) Brute-force 혹은 Generate-and-Test 기법
모든 경우의 수를 테스트한 후, 최종 해법을 도출함
따라서, 일반적으로 경우의 수가 상대적으로 작을 때 유용함 (유한한 시간내에는 해결해야 하니까)
(특징) 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느림, 하지만 해답을 찾을 확률은 높음
- (모든 경우의 수를 전부 뒤져볼 수 있기 때문에 가능함)
- (하지만, 그 경우의 수 중에 정답이 없다면 탐색 실패)
(활용) 주어진 문제를 풀 때, 먼저 exhaustive search 방식으로 접근하여 해답을 도출한 후(= 정답유무 확인), 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것(=최적화)이 바람직함

EXAMPLE: Baby-gin 게임

0~9 사이의 숫자 카드에서 임의의 카드에서 임의의 카드 6장을 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run 이라 하고, 3장의 카드가 동일한 번호를 갖는 경우를 triplete 이라고 하자. 이때 6장의 카드가 run 또는 triplete 로만 구성된 경우를 Baby-gin 으로 부른다.

(Q1) 뽑은 카드가 667767 이면 Baby-gin 인가?

666 / 777 으로 두 개의 triplete 이므로 Baby-gin

(Q2) 뽑은 카드가 054060 이면 Baby-gin 인가?

456 / 000 으로 한 개의 run과 한 개의 triplete 이므로 Baby-gin

(Q3) 101123은 어떤가?

123 / 011 으로 한 개의 run 만을 가지므로 Baby-gin 이 아님

023 / 000 이더라도 한 개의 triplete 이므로 Baby-gin 이 아님

EXAMLPLE: 6자리의 숫자를 입력 받아 exhaustive search 방식으로 Baby-gin 여부를 판단해보자

[step1] 고려할 수 있는 모든 경우의 수 생성하기 (Generate)

6개의 숫자로 만들 수 있는 모든 숫자 나열(중복 포함)

(ex) 입력으로 {2, 3, 5, 7, 7, 7} 을 받았을 경우, 순열(permutation)은 $6!$ 가지 :

$2, 3,5,7,7,7$

$2,3,7,5,7,7$

$\cdots$

$7,7,7,5,3,2$

[step2] 해답 테스트하기 (Test)

(모든 경우의 수에 대해) 앞의 3자리와 뒤의 3자리를 잘라, run 과 triplete 여부를 테스트하고 최종적으로 Baby-gin 을 판단

(sol) 어떤 경우를 하더라도 주어진 6자리 숫자는 235 / 777 과 같은 triplete 만을 가지므로 Baby-gin 아님

input = [2, 3, 5, 7, 7, 7] 

# === Generate === # 
case_list = permutations(input)  # 모든 순열을 얻음

# === Test === # 
for case in case_list:
	""" Run_or_Triplete() : run 또는 triplete 이면 True 를 반환 """ 
	result_1 = Run_or_Triplete(case[:3]) # 앞의 3자리 판별 
	result_2 = Run_or_Triplete(case[3:]) # 뒤의 3자리 판별 

	if result_1 and results_2:
		print("Baby-gin !!!") 
		break

※ 왜 Generate-and-Test 탐색이라 불리는지 알겠지?

덧, Permutation (순열)

“서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것”

(표현) 서로 다른 $n$ 개 중 $r$ 개를 선택하는 순열은 아래와 같이 표현:

$nPr$

(특징1) $nPr$ 은 다음과 같은 식이 성립함:

$nPr = n\times(n-1)\times(n-2)\times\cdots\times(n-(r-1))$

(특징2) $nPn = n!$ 이라고 표기하며 Factorial 이라 부름:

$n! = n\times(n-1)\times(n-2)\times \cdots \times 2\times1$

EXAMPLE: [1, 2, 3]을 포함하는 모든 순열을 생성하는 코드를 만들어보자

동일한 숫자가 포함되지 않을 때, 각 자릿수 별로 loop 를 적용

for i in range(1, 4):  # 첫째 자리
	for j in range(1, 4):  # 둘째 자리
		if j != i:  
			for k in range(1,4): # 셋째 자리
				if k != i and k!=j:
					print(i, j, k)

※ 위의 코드를 일반화 시켜보자

어떠한 길이의 숫자가 시퀀스가 들어와도 순열을 생성할 수 있도록
for-loop 는 최소화 시켜서 Time-complexity 를 줄여보자

Summary

exhaustive search 의 정의와 개념활용
예시를 통해 Generate-and-Test 탐색이라 불리는 이유 확인
(활용 사례) Baby-gin 게임 예시
(덧) Permutation 생성 방법

Reference

[1] https://swexpertacademy.com/main/main.do

Search

컴돌이 도란뇽's AI 스터디 노트