01. List 1 - 3차시 완전 검색(Exhaustive Search)

1. 완전 검색(Exhaustive Search)

 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-force 또는 Generate-and-Test 기법이라고도 불린다. 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다. 일반적으로 경우의 수가 상대적으로 작을 때 유용하다. 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만 해답을 찾아내지 못할 확률이 작다. 따라서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 푼 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.  

 

예시) Baby-gin Game

0 ~ 9사이의 숫자카드에서 임의의 카드 6장을 뽑아, 3장의 카드가 연속되면 run이라하고, 3장의 카드가 동일한 숫자이면 triplete이라고 한다. 이때, 6장의 카드가 run과 triplete으로만 구성되면 baby-gin이라고 한다.

 

예)

1. 667767은 baby-gin이다.

2. 054060은 baby-gin이다.

3. 101123은 baby-gin이 아니다.

 

6자리의 숫자를 입력받아 Baby-gin 여부 찾기

 

1. 고려할 수 있는 모든 경우의 수 생성하기

6개의 숫자로 만들 수 있는 모든 숫자를 나열한다.(중복포함) 입력으로 {2, 3, 5, 7, 7, 7}을 받았을 경우, 아래와 같은 순열을 생성할 수 있다.

모든 경우의 순열 나열

2. 해답 테스트하기

앞의 3자리와 뒤의 3자리를 잘라, run과 triplete여부를 테스트하고 최종적으로 Baby-gin을 판단한다.

해당없음      triplete 

이런 식으로 모든 순열을 생성 후, baby-gin을 판단하고 이러한 방식을 완전 검색이라한다.

 

2. 순열(Permutation)

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

 

1. 서로 다른 n개 중 r개를 택하는 순열

nPr = n * (n - 1) * (n - 2) * ... * (n - r + 1)

 

2. nPn = n!과 같다.

n! = n * (n - 1) * ... * 2 * 1

 

예시) {1, 2, 3}을 포함하는 모든 순열을 생성하는 함수

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

for i1 in range(1, 4):
	for i2 in range(1, 4):
    	if i2 != i1:
        	for i3 in range(1, 4):
            	if i3 != i1 and i3 != i2:
                	print(i1, i2, i3)

 

이것을 기반으로 baby-gin을 판별하는 프로그램을 만들어보자.