반응형
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 |