문제
A,B,C 로 구성할 수 있는 부분집합을 모두 구하시오.
해결 방법
부분집합의 모든 경우의 수가 2^(원소의 개수) 인 것은 학교에서 배우는 내용이다.
코딩 문제에서도 부분집합과 순열, 조합의 경우 해당 개념을 사용하는데, 그 이유는 다음 사진과 같다.
A,B,C를 각각 on off 개념으로 1,0 으로 나타낼 수 있다.
즉, 파이썬에서는 for i in range(2**3) 으로 모든 부분집합을 구할 수 있는 것이다.
예시 코드
비트를 사용하여 부분집합을 구하는 예시입니다.
# 비트를 활용한 부분집합 구하기
letters = ['a', 'b', 'c']
for i in range(1 << len(letters)): # 총 2³, 8개의 경우의 수 체크
selected = []
for j in range(len(letters)): # 각각 비트를 한칸씩 옮기며 대조
if i & (1 << j): # 1칸씩 왼쪽으로 옮겨가며 총 3칸을 대조해본다.
selected.append(letters[j]) # 대조 결과가 성공이라면 selected에 append!
print(selected)
# [] | => (i = 0) => 0 0 0 => 공집합
# ['a'] | => (i = 1) => 0 0 1 => (j = 0)에서 걸려 'a'가 뽑힘
# ['b'] | => (i = 2) => 0 1 0
# ['a', 'b'] | => (i = 3) => 0 1 1
# ['c'] | => (i = 4) => 1 0 0 => (j = 2)에서 걸려 'c'가 뽑힘
# ['a', 'c'] | => (i = 5) => 1 0 1
# ['b', 'c'] | => (i = 6) => 1 1 0
# ['a', 'b', 'c'] | => (i = 7) => 1 1 1
'알고리즘 문제 풀이 > 알고리즘 이론 공부' 카테고리의 다른 글
9장 Theory of NP (0) | 2023.07.30 |
---|---|
8장 Theory of computational complexity (0) | 2023.07.30 |
7장 Theory of computational complexity : Sorting problem (0) | 2023.07.30 |
6장 Branch and bound Algorithm (0) | 2023.07.30 |
5장 Backtracking Algorithm (0) | 2023.07.30 |