[2024.02.28] 부분집합, 조합 / 그리디

부분 집합

: 집합에 포함된 원소들을 선택하는 것

구현 방법:
1) 완전탐색
O, X로 집합에 포함시킬지 말지 결정

arr = ['O', 'X']
path = []
name = ['MIN', 'CO', 'TIM']

def print_name():
    print('{', end = '')
    for i in range(3):
        if path[i] == 'O':
            print(name[i], end = ',')
    print('}')

def run(lev):
    if lev == 3:
        print_name()
        return

    for i in range(2):
        path.append(arr[i])
        run(lev+1)
        path.pop()

run(0)

2) Binary Counting

arr = ['A', 'B', 'C']
n = len(arr)

def get_sub(tar):
    for i in range(n):
        if tar & 0x1: #1비트가 1인지 확인
            print(arr[i], end='')
        tar >>= 1

for tar in range(1 << n):
    print('{', end='')
    get_sub(tar)
    print('}')

• 원소 개수가 2개 이상인 부분집합의 개수

arr = ['A', 'B', 'C', 'D', 'E']
n = len(arr)

def get_sub(tar):
    cnt = 0
    for i in range(n):
        if tar & 0x1: #1비트가 1인지 확인
            cnt += 1
        tar >>= 1 #오른쪽 끝 비트를 하나씩 제거
    return cnt

result = 0
for tar in range(1 << n):
    if get_sub(tar) >= 2:
        result += 1

print(result)

조합

[도전] {A, B, C, D, E} 5명 중 3명 뽑을 수 있는 모든 경우의 수

ABC 123
ABD 124
ABE 125
ACD 134
ACE 135
ADE 145
BCD 234
BCE 235
BDE 245
CDE 345

[도전] 주사위 던지기
주사위 눈금 N개를 던져서 나올 수 있는 모든 조합 출력하기

N = 3
path = []

def func(lev, start):
    if lev == N:
        print(path)
        return

    for i in range(start, 7):
        path.append(i)
        func(lev+1, i)
        path.pop()

func(0, 1)

탐욕(Greedy) 알고리즘

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

[도전] 화장실 문제

wait = [15, 30, 50, 10]
wait.sort()
total = 0

while wait:
    total += wait[0] * (len(wait)-1)
    wait.pop(0)

print(total)

[도전] fractional Knapsack 문제

n = 3 #물건 3개
target = 30 #knapsack 30kg
things = [(5, 50), (10, 60), (20, 140)] #(kg, price)

#kg 당 가격으로 내림차순 정렬
things.sort(key = lambda  x : (x[1] / x[0]), reverse=True)

sum = 0

for kg, price in things:
    per_price = price / kg
    #만약 가방에 남은 용량이 얼마 되지 않는다면, 물건을 잘라 가방에 넣고 끝난다
    if target < kg:
        sum += target * per_price
        break

    sum += price
    target -= kg

print(int(sum))

[도전] 회의실 배정 문제

time = [(5,9), (6,10), (8,11), (1,4), (3,5), (1,6), (5,7), (3,8), (2,13), (12,14)]
time.sort(key=lambda x: x[1], reverse=True)

end_time = time.pop()[1]
ans = 1

while time:
    s, e = time.pop()
    if s >= end_time:
        end_time = e
        ans += 1

print(ans)

<연습문제> 부분집합의 합 문제