조합적 문제

부분 집합 (powerset)

: 어떤 집합의 공집합과 자기자신을 포함한 모든 부분

• 집합에서 부분 집합을 찾아내는 구현 방법
  1. 완전탐색
     • 재귀호출을 이용한 완전탐색으로, 부분 집합을 구할 수 있음
     • 실전 보다는 완전 탐색 학습용으로 추천하는 방법
  2. Binary Counting
     • 2진수 & 비트연산을 이용하여 부분 집합을 구할 수 있음
     • 모든 부분 집합이 필요할 때 사용하는 추천 방법

Binary Counting

• 어떤 집합의 원소 수가 N개라면, 가능한 부분집합의 개수는 2^N개임.

• 각 부분집합은 N자리의 이진수 비트열로 표현할 수 있음.

  • 1 → 해당 원소 포함
  • 0 → 해당 원소 미포함

  10진수	이진수	부분집합
  0	000	∅
  1	001	{A}
  2	010	{B}
  3	011	{A, B}
  4	100	{C}
  5	101	{A, C}
  6	110	{B, C}
  7	111	{A, B, C}

• 부분 집합의 총 개수

  • 만들 수 있는 집합의 총 개수는 2^n이며 n=3이기 때문에, 총 8개의 부분 집합 존재
  • 2^n은 1<<n 공식을 이용하여 빠르게 구할 수 있음

• 부분 집합 코드

  arr = ['A', 'B', 'C']   # 원소가 들어있는 리스트
  n = len(arr)            # 원소 개수 (n=3)
  
  def get_sub(tar):
      # tar: 부분집합을 나타내는 이진수 값 (0 ~ 2^n - 1)
      for i in range(n):  
          # i: arr에서 현재 검사할 원소의 인덱스
          if tar & 0x1:  
              # tar의 마지막 비트가 1이면 해당 원소 포함
              print(arr[i], end='')
          # 검사한 비트를 버리고 오른쪽으로 한 칸 이동
          tar >>= 1        
  
  # 1 << n = 2^n → 부분집합의 총 개수
  for tar in range(1 << n):   # range(0, 8) → 0~7
      print('{', end='')      # 부분집합 시작 괄호 출력
      get_sub(tar)            # 현재 tar(이진수)에 해당하는 부분집합 구하기
      print('}')              # 부분집합 닫는 괄호 출력
  

탐욕 알고리즘 (Greedy)

Greedy

: 결정이 필요할 때, 현재 기준으로 가장 좋아 보이는 선택지로 결정하여 답을 도출하는 알고리즘

<aside> 🚫

그리디는 쉬워 보이나, 예외 없이 모든 경우가 맞는 규칙인지 아닌지 증명이 어려움

</aside>

Knapsack 문제

<aside> ❓

도둑이 보물들이 있는 창고에 침입하였다. 도둑은 최대 30kg까지 짐을 담아갈 수 있다.

물건의 개수(N) 그리고 물건 별 무게(W)와 가격(P)이 주어질 때, 어떤 물건을 담아야 도둑이 최대 이득을 볼 수 있을지 구하시오.

• kg 당 가치가 가장 높은 것을 먼저 담으면 안됨
  • Greedy로 접근하면 안되는 예외 케이스가 존재함
  • 완전 탐색 or DP로 접근해야 함

탐욕 알고리즘 4가지 Tip

1. 문제 유형 파악하기 - "최적화 문제인가?"

⇒ 가장 먼저, 문제의 요구사항이 최적화 문제인지 확인해야 합니다.