부분집합

예시) 집합에 포함된 원소들을 선택하는 것이다.

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

집합에서 부분 집합을 찾아내는 구현 방법

완전 탐색 (학습용으로만 추천)
Binary Counting (비트연산) (실전용)

바이너리 방식 예시) 친구 5명중 최소 2명이상으로 구성될 경우

friends = ['a','b','c','d','e']
n = 5 # 친구의 수
m = 2 # 2명이상
# 5P2
def getFriend(tar):   cnt = 0   for i in range(n):     # 1비트 1인지 확인     if tar & 0x1:       # print(friends[i], end='')       cnt += 1     # right shift 비트 연산자 -> 오른쪽 끝 비트를 하나씩 제거     tar >>= 1   return cnt
# getFriend(m)
result = 0
for j in range(1<= m: # bit가 2개이상 1이라면 -> 2명 이상이라면?     result += 1
print(result)

# 같은 결과를 도출함
n = 3
# 첫 번째 방법
for i in range(1<>= 1   print()

조합 Combination

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

friends = ['a','b','c','d','e']
m = 5 # 친구의 수
n = 3

# 반복문 방법
for a in range(5):
  start1 = a+1
  for b in range(start1,5):
    start2 = b + 1
    for c in range(start2,5):  print(arr[a], arr[b], arr[c])

# 재귀 방법
path = []
# 5C2
def getFriend(lev, start):   if lev ==n:     print(path)     return    for i in range(start,5):     path.append(friends[i])     getFriend(lev + 1, i+1)     path.pop()

getFriend(0,0)

예제) 주사위 3개 던지기 조합 (중복 조합)

n = 3
path = []
def qube(lev,start):   if lev == n:     print(path)     return    for i in range(start,7):     path.append(i)     qube(lev+1,i)     path.pop()

qube(0,1)

주의할 점 : [A,A] 은 가능하지만 [A,B] 와 [B,A] 는 같이 있을 수 없다. = 조합이니까

Greedy

결정이 필요할 때, 현재 기준으로 가장 좋아 보이는 선택지를 결정해서 값을 도축하는 알고리즘

대표적인 방법

완전탐색 : 모든 경우의 수
Greedy : 가장 좋아보이는 수
DP : 과거의 데이터를 이용해서 현재의 데이터를 만들어 내는 것
분할정복

예제) 화장실 문제

arr = [15,30,50,10]
arr.sort()
sum = 0
for i in range(len(arr)):   sum +=arr[i] * (len(arr)-1-i)

print(sum)

예제2)

0-1 knapsack ( 고체류 물건)

도둑이 최대 30kg까지 짐을 담아갈 수 있을 때,

물건의 개수 n, 물건 별 무게(w), 가격(p)

⇒ 1kg당 가격으로 접근하기 ⇒ 그리디로 못푼다. 부분집합으로 풀어야 함

fractional knapsack 만약 물건을 원하는 만큼 자를 수 있을 때 (액체류 물건)

⇒ 그리디 성립해서 풀이 가능

n = 3
target = 30
things = [(5, 50), (10, 60), (20, 140)]
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))

예제 3) 활동선택 문제

(1,4),(3,5),(1,6) ... (12,14)

회의 종료시간이 가장 빠른 회의를 먼저 선택하면 된다.

종료시간을 기준으로 회의들을 오름차순 정렬한다.

종료시간이 가장 빠른 회의를 찾자마자 확정 (1,4)

⇒ 이제 4시 이후로 부터 회의가 가능하다.

4시 이후에 가장 빨리 끝나는 회의 찾기 (5,7)

⇒ 이제 7시 이후로 회의가 가능

7 시 이후로 가장 빨리 끝나는 회의 찾기 (8,11)

⇒ 이제 11시 이후로 회의가능

11시 이후로 가장 빨리 끝나는 회의 (12,14)

⇒ 정답은 4회

문제 전략

끝나는 시간을 기준으로 오름차순 정렬
빠르게 끝나는 회의를 선택하여 확정한다.
이후로 가능한 회의 중, 빠르게 끝나는 회의를 선택하여 확정한다.