[코드트리 챌린지] 8주차 - 그리디

1. 대표 유형 및 핵심

1) 동전 거슬러주기

→ 주어진 동전들이 전부 배수관계일 때 ,큰 동전이 사용이 가능하다면 작은 동전을 사용하는 것보다 항상 좋은 선택

예제: https://www.codetree.ai/cote/19/problems/add-coins?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

2) 연속 부분 합의 최댓값 구하기

→

예제: https://www.codetree.ai/cote/19/problems/implement-fractional-knapsack?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

3)쪼개어 배낭 채우기(Fractional Knapsack)

→ 상황: 무게 K 까지 담을 수 있는 가방이 존재한다. 보석의 가격과 무게가 주어졌을 때, 보석을 쪼개서도 가져갈 수 있다. 가방에 담을 수 있는 보석의 최대 가치는 얼마인지 구하는 프로그램을 작성하자.

→ 쪼갤 수 있는 경우에는 "무게 대비 가치"가 높은 것을 먼저 가방에 넣는게 좋다. 따라서 "가격/무게"로 내림차순 정렬해서 가져갈 것을 선택한다.

예제: https://www.codetree.ai/cote/19/problems/implement-fractional-knapsack?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

→ 쪼갤 수 없는 경우: DP(0/1 Knapsack) 

 

4) 숫자 합치기

→ 상황: n개의 숫자에 대해서 2개씩 뽑아 n개의 숫자를 모두 합치려고 한다. 이 때, 뽑은 숫자를 a, b라고 했을 때 a와 b를 합하는데 드는 비용은 a+b이다. 비용이 최소가 되도록 프로그램을 작성하자.

→ 숫자의 순서에 상관없이 작은 값 2개씩을 뽑아 더하면 된다.

→ https://www.codetree.ai/cote/19/problems/%08merge-numbers/introduction

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

5) 회의실 준비

- 다음 주-

6) 최대 숫자 만들기

- 다음 주-

2. 코드(Python) - 숫자합치기

from heapq import heappush, heappop

n = int(input())
nums =list(map(int, input().split()))

heap = []
cost = 0
# len() N , min N > N^2 > 시간초과
# 최솟값을 추출 -> heapq 사용

for x in nums:
    heappush(heap, x)

while len(heap) >= 2:
    q1 = heappop(heap)
    q2 = heappop(heap)
    cost += (q1+q2)
    heappush(heap, q1+q2)
    
print(cost)

※ 실력진단

PS. 8주가 끝났다...흑..우테코까지 병행하니까 쉽지 않더라..이후에 시뮬레이션, 자료구조에도 집중하는게 좋아보인다. 비록 끝까지 열심히 하지는 못했지만 도움이 많이 되었다.