Exhaustive

완전 검색, 고지식 (Brute force)

[알고리즘] 완전 검색, 무차별 대입 검색(Brute Force Search) 순차 검색 Searching 이거 해 보고 다른 알고리즘으로 성능 개선 모든 경우의 수 생성 후 다 더해 봄

• ex) 부분 집합 갯수 구하려면 원소 갯수만큼 for문 돌리기, in / not 사용 → 비효율

- 적용 예시: 부분 집합의 합

유한한 정수 집합의 부분 집합의 합이 0되는 경우 있는지 찾기 ex) (-7, -3, -2, 5, 8) → (-3, -2, 5) 전체 부분 집합의 갯수: 2^(원소의 갯수) → 원소 있다 / 없다의 0 / 1 비트 문제로 치환 가능 이 경우 비트는 index의 역할

• 비트연산자 활용 Bitwise

  full_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
  n = 10 #원소 갯수 n = len(arr) 
  for i in range (1<<n): #전체 부분집합 갯수만큼 돎
   
        for j in range (n): 
            if i & (1<<j): #->이게 핵심!
                temp_list.append (subset[j]) # , end= ","는 print에만 쓸 수 있는 함수
                ```

• 시프트 연산자 (<<, >>, >>>): 비트들을 다른 자릿수로 이동시키는 방식으로 동작한다.

• 비트 = 2진수이므로 자릿수 옮기는 건 2씩 곱하기 / 나누기

• If i & (1<<j):

  전체 부분 집합 갯수 → 집합 원소 (들어감 / 안 들어감) 모든 경우 실험해서 출력

  case 1) i == 3, n = 5, full_list = [1, 2, 3, 4, 5] 
  i는 이진수로 11, 이 경우에 모든 j는 0 ~ 4 순회하면서 2^j를 만듦 (<<연산자로 2배씩 계속 곱함)
   
   j == 0: 11 - 1
   j == 1: 11 - 10
   j == 2: 11 - 100
   j == 3: 11 - 1000
   j == 4: 11 - 10000
   
   -> &연산자는 모두 1이어야 1, 나머지는 0.
   -> if는 0만 아니면 True
   
  j == 0:
   11
   01
   --
   01 -> 1, True
   
   j == 1:
   11
   10
   --
   10 -> 2, True
   
   j == 2 ~ 4:
   11
   00
   --
   00 -> 0, False
   
   
  -> 최종 출력: full_list[0], full_list[1] # 1, 2