부분집합
부분집합
집합에 포함된 원소들을 선택하는 것이다.
부분집합의 예시
{A, B, C}의 부분집합
{}, {A}, {B}, {C}, {A, B}, {B, C}, {A, B, C}
부분집합에는 아무것도 선택하지 않은 경우도 집합에 포함된다.
집합에서 부분집합을 찾아내는 구현 방법
- 완전 탐색
재귀호출을 이용한 완전탐색으로 부분집합을 구할 수 있다.
실전보다는 완전탐색 학습용으로 추천
- Binary Counting
2진수 & 비트연산을 이용하여 부분집합을 구할 수 있다.
부분집합이 필요할 때 사용하는 추천 방법
완전탐색으로 부분집합 구하기
민철이에게는 세명의 친구가 있다.
{MIN, CO, TIM}
함께 영화관에 갈수 있는 멤버를 구성하고자 한다.
모든 경우의 수를 출력해보자
Branch 2개
level 3개
arr = ['O', 'X']
path = []
name = ['MIN', 'CO', 'TIM']
def print_case():
print('{ ', end = ' ')
for i in range(3):
if path[i] == 'O':
print(name[i], end = ' ')
print('}')
def run(lev):
if lev == 3:
print_case()
return
for i in range(2):
path.append(arr[i])
run(lev + 1)
path.pop()바이너리 카운팅 (Binary Counting)
원소 수에 해당하는 N개의 비트열을 이용한다.
0 0 1 이면 {A}임을 나타냄
1 1 0 이면 {B, C}임을 나타냄
집합의 총 개수
만들 수 있는 집합의 총 개수는 2**n 이며 n ==3 이기에 총 8 개 집합이다.
2**n 공식은 1 <<n 공식을 이용해서 빠르게 구할 수 있음
print(pow(2, 3))
print(1 << 3)A, B, C의 부분집합 구하기
arr = ['A', 'B', 'C']
n = len(arr)
def get_sub(tar):
for i in range(n):
if tar & 0x1: # 비트연산을 이용하여 마지막 한 자리가 1인지 0인지 검사한다.
print(arr[i], end = '')
tar >>= 1 # 검사한 한 자리를 제거한다.
for tar in range(0, 1<<n):
print('{', end = '')
get_sub(tar)
print('}')부분집합 문제
민철이는 친구 {A, B, C, D, E}가 있다. 이 중 최소 2명 이상의 친구를 선정하여 함께 카페에 가려고 한다. 총 몇가지 경우가 가능할까?
arr = ['A', 'B', 'C', 'D', 'E']
n = len(arr)
def get_count(tar):
cnt = 0
for i in range(n):
# 1 비트 1인지 확인
if tar & 0x1:
cnt += 1
# right shift 비트 연산자 -> 오른쪽 끝 비트를 하나씩 제거
tar >>= 1 # 오른쪽으로 하나씩 이동
return cnt
result = 0
for tar in range(1 << n):
if get_count(tar) >= 2: # bit가 2개 이상 1이라면 -> 2명 이상이라면
result += 1
print(result)
조합
조합
서로 다른 n개의 원소 중 r개를 순서 없이 골라낸 것을 조합(combination)이라고 부른다.
순열과 조합의 차이
순열
{A, B, C, D, E} 5명 중 1등, 2등, 3등 뽑기
- A, B, C 와 C, B, A는 다른 경우이다.
조합
5 명 중 3명 뽑기
- A, B, C 와 C, B, A는 같은 경우이다.
조합 연습 문제
{A, B, C, D, E} 5명 중 3명을 뽑을 수 있는 모든 경우의 수를 적어보자
arr = ['A', 'B', 'C', 'D', 'E']
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])만약 5명 중 3명을 뽑는 코드는 몇 중 for 문이 필요할 까?
3중 for로 구현 가능하다.
만약 5명 중 n 명을 뽑는 코드는 몇 중 for 문이 필요할까?
n 중 for로 구현이 가능하다. 즉, 재귀호출 구현이 필요
branch : 최대 5개
level : n
재귀호출로 조합 구현하기
arr = ['A', 'B', 'C', 'D', 'E']
path = []
n = 3
def run(lev, start):
if lev == n:
print(path)
return
for i in range(start, 5):
path.append(arr[i])
run(lev + 1, i + 1)
path.pop()
run(0, 0)조합 도전문제
주사위 던지기
주사위 눈금 N개를 던져서 나올 수 있는 모든 조합을 출력하시오. (구현)
N = 3 일때 출력 결과
N = 3
path = []
def func(lev, start):
if lev == N:
print(path)
return
# i 부터 트리에 진입
for i in range(start, 7): # start는 i로 받음
path.append(i)
func(lev+1, i) # 중복 순열에서 start만 추가
path.pop()
func(0, 1) # 주사위 시작은 1임그리디
그리디 (Greedy)
결정이 필요할 때, 현재 기준으로 가장 좋아보이는 선택지로 결정하여 답을 도축하는 알고리즘
대표적인 문제해결방법
- 완전 탐색 (Brute-Force)
답이 될 수 있는 모든 경우를 시도해보는 알고리즘
- Greedy
결정이 필요할 때 가장 좋아보이는 선택지로 선택하는 알고리즘
- DP
현재에서 가장 좋아보이는 것을 선택하는 것이 아니라, 과거의 데이터를 이용하여 현재의 데이터를 만들어내는 문제해결기법
- 분할정복
큰 문제를 작은 문제로 나누어 해결하는 방법
10, 50, 100, 500원 동전일 때 1730원을 거슬러 주는 소스 코드
coin_list = [500, 100, 50, 10]
tar = 1730
cnt = 0
for coin in coin_list:
possible_cnt = tar // coin # 사용 가능한 동전의 수 (만약 500원이라면 3개 가능)
cnt += possible_cnt # 3개를 추가한다.
tar -= coin * possible_cnt # 3개로 만들 수 있는 금액인 1500원을 뺀다.
print(cnt)그리디 도전 문제
화장실 대기시간 누적합이 최소가 될 수 있게 구현해라
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)그리디 도전 문제
도둑은 보물들이 있는 창고에 침입하였다.
도둑은 최대 30kg 까지 짐을 담아갈 수 있다.
물건의 개수 (N) 그리고 물건 별 무게 (W)와 가격 (P)이 주어질 때, 어떤 물건을 담아야, 도둑들이 최대 이득을 볼 수 있을지 구하시오.
Fractional Knapsack 문제 해결 방법
그리디가 성립한다.
Kg당 가격이 가장 높은 물건을 최대한 담으면 된다.
n = 3
target = 30
things = [(5, 50), (10, 60), (20, 140)]
# (Price / kg) 기준으로 내림차순 sort
things.sort(key= lambda x : (x[1] / x[0]), reverse= True)
# sort 결과 = [(5, 50), (20, 140), (10, 60)]
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))회의실 배정
문제 해결 방법
회의 종료시간이 가장 빠른 회의를 먼저 선택하면 된다.
