[Advanced] 2. 완전 검색 - 이론편

베이비진(Baby-Gin) 문제

0~9 사이의 숫자 카드에서 임의의 카드 6장 뽑음

• 3장의 카드가 연속적인 번호를 갖는 경우 런(Run)
• 3장의 카드가 동일한 번호를 갖는 경우 트리플릿(Triplete)

=> 6장의 카드가 Run과 Triplete으로만 구성된 경우 Baby-Gin!

ex) 667767 - 두개의 Triplete 666, 777

 

완전 검색

• 문제의 해를 얻기 위해 가능한 모든 경우들을 나열해 보고 확인하는 기법
• 문제를 해결하기 위한 간단하고 쉬운 접근법
• 대부분의 문제에 적용 가능
• 문제에 포함된 자료의 크기가 작을 경우 유용

단점

• 문제의 크기가 커지면 시간 복잡도가 매우 크게 증가
• 수행 속도가 느리지만, 해답을 찾아내지 못할 확률이 적음
• 그리디 기법이나 동적 계획법을 이용해서 효율적인 알고리즘을 찾아야 함

 

고지식한 검색 (순차 검색, Sequential Search)

자료들의 리스트에서 키 값을 찾기 위해 첫 번째 자료부터 비교하면서 진행 

 

완전 검색을 통한 Baby-Gin 접근

1. 고려할 수 있는 모든 경우의 수 생성하기
   입력으로 {2,3,4,7,7,7}을 받은 경우, 다음과 같이 순열 생성
   2 3 5 7 7 7 / 2 3 7 5 7 7 7 / ... / 7 7 7 5 3 2
2. 앞의 세 자리와 뒤의 세 자리를 잘라서, Run과 Triplete여부를 각각 판단
3. 최종적으로 베이비진 판단

문제점

위의 예시에서 숫자 7 세개가 반복되면서 중복이 생김
이것을 제거할 수 있다면 계산 시간 단축 가능

 

조합적 문제

완전 검색은 많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 검색이다.
이것은 순열, 조합, 부분집합과 같은 조합적 문제들과 관련이 있다.
완전 검색은 조합적 문제에 대한 Brute-force 방식이다.

순열

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

서로 다른 n개 중 r개를 택하는 순열 
nPr = n(n-1)(n-2)...(n-r+1)

ex) {1,2,3,4} 순열
순열의 수 : 4! = 24

대표적인 문제로 외판원 문제가 있음.

외판원 문제

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어짐
출발 도시에서 시작해서 다른 도시들을 모두 한 번씩 돌고 돌아오는 최소 비용 경로를 구하는 문제

순열을 통해 푼다면? n!
=> n이 증가함에 따라 실행 시간이 기하급수적으로 증가

itertools 이용

import itertools

a = ['A', 'B', 'C']
result = itertools.permutations(a) # 순열 nPn
result = itertools.permutations(a, r) # 순열 nPr

print(list(result))

교환을 통한 선택

# a[] : 데이터가 저장된 리스트
# n : 원소의 개수
# k : 지금까지 선택된 원소의 수
def perm(n, k):
    if k == n: # 하나의 순열이 생성됨
        print(a)
    else:
    	for i in range(k, n):
            a[k], a[i] = a[i], a[k] # 교환을 통한 선택
            perm(n, k+1) # 재귀호출
            a[k], a[i] = a[i], a[k] # 이전 상태로 복귀

 

 

부분집합

집합에 포함된 원소들을 선택하는 것
다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것

바이너리 카운팅을 통한 부분집합 생성
원소 수에 해당하는 N개의 비트열을 이용

A # 집합
N = len(A)

for i in range(1<<N): # 2^N 만큼 반복
	part = [] # 부분 집합이 들어갈 리스트
    for j in range(N):
    	if i & (1<<j):
        	part.append(A[j]) 
	print(part) # 부분집합 중 하나

 

조합

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것. nCr = n!/(n-r)!r!

라이브러리 이용

import itertools
a = ['A','B','C']
result = itertools.combinations(a, r=2) # 조합 nCr
result = itertools.combinations_with_replacemnet(a, r=2) # 중복조합 n개 중에 2개
print(list(result))

재귀 호출을 이용한 조합 생성
5C3 = 4C2+4C3 과 같이 조합을 나누어 생각함
예를 들어, 12345에서 5를 제외한 4C2의 경우의 수와 5를 제외한 4C3의 경우의 수를 합한 것과 같음

# a[] : n개의 원소를 가진 리스트
# tr[] : 조합이 임시 저장될 크기 r인 리스트

def comb(n,r):
    if r==0:
    	print(tr)
    elif n < r:
    	return
    else:
    	tr[r-1] = a[n-1] # 예시에서의 5
        comb(n-1, r-1) # 4C2
        comb(n-1, r)   # 4C3