부분 집합, 조합, 탐욕 알고리즘

• 부분 집합

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

아무것도 선택하지 않은 경우 (공집합)도 부분 집합에 포함된다.

부분 집합 구현 방법 : 완전 탐색 / binary counting

 

• binary counting 을 이용한 부분 집합 탐색 코드

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

def get_count(tar):
    count = 0
    for i in range(n):
        # 1비트 1인지 확인
        if tar & 0x1:
            count += 1
        # right shift 비트 연산자를 사용하여 오른쪽 끝 비트를 하나씩 제거
        tar >>= 1
    return count

result = 0
for tar in range(1 << n):
    if get_count(tar) >= 2:     # bit 가 2개 이상 = 2명 이상
        result += 1
print(result)

 

• 조합

서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것

5명 중 3명을 뽑으면 3중 for문이 필요

만약 5명 중 n명을 뽑으면 n중 for문이 필요해서 재귀 호출을 사용한다!

 

• 주사위 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 → 결정이 필요할 때, 현재 기준으로 가장 좋아 보이는 선택지로 결정하여 답을 도출한다.

 

대표적인 문제해결기법들

→

완전 탐색 : 답이 될 수 있는 모든 경우를 시도해보는 알고리즘

Greedy : 결정이 필요할 때 가장 좋아보이는 선택지로 결정하는 알고리즘

DP : 현재에서 가장 좋아 보이는 것을 선택하는 것이 아니라, 과거의 데이터를 이용하여, 현재의 데이터를 만들어내는 문제해결기법

분할정복 : 큰 문제를 작은 문제로 나누어 해결하는 문제해결기법

 

• 그리디 알고리즘 문제

arr = [15, 30, 50, 10]
arr.sort()
count = 0

for i in range(len(arr)):
    count += arr[i] * (len(arr) - i - 1)

print(count)

person = [15, 30, 50, 10]
n = len(person)
person.sort()
sum = 0
left_person = n - 1     # 화장실 이용 못한 대기자 수

for turn in range(n):
    time = person[turn]
    # 누적합 = 남은 사람 * 시간
    sum += left_person * time
    left_person -= 1
print(sum)

 

• 도둑 문제

n = 3
target = 30
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))

 

• 회의실 문제

가장 빨리 시작하는 회의들 중 가장 빨리 끝나는 회의를 선택

가능한 회의 추리기

(반복)

 

• 조합 짜는 법

arr = 'ABCD'
N = len(arr)
R = 3
# 4C3
# 첫 번째 요소를 선택
pick = [0] * R    # 조합 요소로 선택한 값을 저장하기 위해 미리 준비한 공간
def comb(k, start):
    if k == R:
        print(*pick)
        return

    for i in range(start, N):
        # 두 번째 요소를 선택
        pick[k] = arr[i]   # 선택한 값을 덮어씌운다.
        comb(k + 1, i + 1)
comb(0, 0)

파이썬에서는 리스트가 쓰기 편해서 append, pop을 사용해서 선택하고 재귀호출을 하지만,

다른 언어에서는 그렇게 쓰기보다는 위 코드의 pick 같은 공간을 미리 만들어놓고

선택한 값을 준비한 공간에 덮어쓰는 방식을 많이 쓴다.