[Algorithm] 완전 탐색

* Python을 기준으로 합니다

---

완전 탐색 (Brute-Force)

- 개념

• 완전 탐색 : 모든 경우의 수를 확인해서 정답을 구하는 방법
  • 완전 탐색의 적용 : 현재 위치에서 다음 위치로 이동할 수 있는 모든 조건들을 정의해야 함
    - 반복적으로 적용되는 동일 조건으로 정답을 찾아야 하는 경우
    - 입력 크기가 작을 때 최적해를 구해하는 경우
    - 여러 조합들 중에서 최적해를 찾아야하는 경우
  • 완전 탐색의 유형들
    1. 단순 완전 탐색
       - 반복문, 조건문을 활용하여 단순하게 모든 경우의 수들을 확인하는 방법
       
    2. 순열, 조합
       - 여러 데이터에서 경우의 수를 만들어서 활용하는 방법
       - 순열 (Permutation) : 서로 다른 $n$개에서 $r$개를 선택할 때, 선택되는 순서가 중요한 경우
       - 조합 (Combination) : 서로 다른 $n$개에서 $r$개를 순서에 상관없이 선택하는 경우
       - 중복순열/중복조합 : 동일한 데이터를 중복해서 선택하는 것이 가능한 순열/조합
    3. 비트마스크
       - 2진수를 활용해서 배열을 탐색, 조회하는 방법
       - 배열이 커서 탐색하는 것이 까다롭거나 특정 규칙으로 변경하는 경우 사용
    4. 재귀
       - 재귀 호출 시 모든 경우의 수를 탐색해야 하는 경우
       
    5. DFS/BFS
       - DFS는 스택을 사용해서 구현하고, 한 방향의 모든 탐색을 수행할 때까지 진행하는 방식
       - BFS는 큐를 사용해서 구현하고, 현재 위치에서 탐색 가능한 모든 방향을 확인하는 방식
       - 모든 경우의 수를 탐색해야 하는 경우 DFS를 활용하고, 최단 거리/최소 비용과 같은 최적해를 찾아야 하는 경우 BFS가 유리 

- 구현

1. itertools를 활용한 순열, 조합

• `itertools` 라이브러리는 순열, 조합을 지원함
  • `permutations(배열, 개수)` : 순열 계산
  • `combinations(배열, 개수)` : 조합 계산
  • `product(배열, 개수)` : 중복 순열 계산
  • `combinations_with_replacement(배열, 개수)` : 중복 조합 계산

import itertools

test = [1,2,3]

for x in itertools.permutations(test, 2): # 순열
  print(x, end=' ') #(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 
print()
for x in itertools.combinations(test, 2): # 조합
  print(x, end=' ') #(1, 2) (1, 3) (2, 3) 
print()
for x in itertools.product(test, repeat=2): # 중복 순열
  print(x, end=' ') #(1, 1) (1, 2) (1, 3) (2, 1) (2, 2) (2, 3) (3, 1) (3, 2) (3, 3) 
print()
for x in itertools.combinations_with_replacement(test, 2): # 중복 조합
  print(x, end=' ') #(1, 1) (1, 2) (1, 3) (2, 2) (2, 3) (3, 3)

2. 비트마스크

• 비트 연산자의 종류
  • `A & B` : AND 연산
  • `A | B` : OR 연산
  • `~A` : NOT 연산
  • `A ^ B` : XOR 연산
  • `A << B`, `A >> B` : A를 B만큼 왼쪽/오른쪽으로 shit

arr = [1,1,0,1,0]

#위 배열에서 1,2,3번 index가 모두 1인지 확인
arr_bit = 0b11010
bit = 0b01110

print((arr_bit&bit) == bit) #False

• 비트 연산으로 배열의 모든 부분집합 구하기

arr = [1,2,3]

for i in range(1<<len(arr)): #bit 연산
  print('{ ',end='')
  for j in range(len(arr)):
    if (i&(1<<j)): #bit 연산
      print(arr[j], end=' ')
  print('}')

'''
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }
'''

비트 연산을 이용한 부분집합 구하기