오도원입니다.

건강과 행복을 위하여

컴퓨터공학/알고리즘

Algorithm. 백트래킹 - 부분집합

오도원공육사 2020. 5. 22. 10:58
반응형

1. Power set

  • 집합의 모든 부분집합 (공집합, 자기자신 포함)
  • 집합의 원소개수가 n => 부분집합의 개수는 2^n
  • 1 또는 0 값을 가지는 비트열 리스트로 부분집합 표현

부분집합 상태 공간 트리

소스코드

# a[0, ... , n-1] : 집합에 대한 비트표현 저장, 크기는 원소의 수
# k : 선택한 횟수(현재 노드의 높이)
# n : 모든 선택 수(트리의 높이)

def subset(a, k, n):
    if k == n: # 모든 선택이 끝난 상태 (단말노드 도착)
        process_solution(a, n) # 
    else:
    	a[k] = 0 # k번째 원소 포함 안하는 경우
        subset(a, k+1, n)
        a[k] = 1 # k원소 포함하는 경우
        subset(a, k+1, n)

 

백트래킹 구현은 상태공간트리와 동일한 함수호출트리가 되도록 재귀호출을 구현하는 것이다.

재귀호출트리, 위의 상태 공간 트리와 형태가 동일하다

 

반응형

'컴퓨터공학 > 알고리즘' 카테고리의 다른 글

Algorithm. 백트래킹 - 동전 거스름돈  (0) 2020.05.22
Algorithm. 백트래킹 - 순열  (0) 2020.05.22
Argorithm. 백트래킹  (0) 2020.05.22
부분집합 bitwise 표현  (0) 2020.05.18
Algorithm. 2주차 스터디 계획  (0) 2020.05.17