[Python] 그리디 알고리즘 문제풀이 (3)

 

이코테 책에서 풀다가 복습할 문제들만 정리해본다.

자세한 문제는 '이것이 코딩테스트다 with 파이썬 (나동빈)' 책에서 확인하기

 

1️⃣ 만들 수 없는 금액 (K 대회 기출)

N개의 동전으로 양의 정수 금액 중 만들 수 없는 최솟값을 구하는 프로그램을 작성하라.

첫번째 풀이) 1원부터 만들 수 있는 최대값까지 주어진 N개의 동전으로 만들 수 있는지 확인해야 하므로 먼저 화폐 단위를 내림차순으로 정렬한다. 예를 들어 3, 2, 1, 1, 9 가 주어졌다면 9, 3, 2, 1, 1 로 정렬한다. 그리고 1원부터 주어진 동전 조합으로 만들 수 있는지 coin[0]부터 체크한다. 즉, 9부터 3, 2, 1, 1 순으로 1원을 만들 수 있는지 확인하고 coin[3] = 1로 만들 수 있음을 확인하면 다음 숫자인 2원을 만들 수 있는지로 넘어간다. 2원은 coin[2] = 2로 만들 수 있다. 이렇게 반복하다보면 8원은 coin[1:]를 다 더해도 구할 수 없음을 깨닫는다.

# solution 1 
# 화폐 단위가 큰 것부터(내림차순) 만들 수 있는 금액 계산
n = int(input())
coin = list(map(int, input().split()))
answer = 1
coin.sort(reverse=True)
while True:
    temp = answer
    for i in coin:
        if temp >= i:
            temp -= i
    if temp == 0:
        answer += 1
    else:
        break
print(answer)

두 번째 풀이) 화폐 단위를 작은 것부터 만들 수 있는 최고금액을 갱신해나간다는 아이디어로 더 직관적으로 풀 수 있다. 직관적인 그리디 알고리즘인데, 가장 작은 동전 1원으로는 1원 하나를 만들 수 있다. 그러므로 answer = 2로 다음 금액 타깃을 정한다. 동전 1원, 1원 두 개로는 1원, 2원을 만들 수 있으므로 answer = 3 이 된다. 만약 1원, 1원, 3원 3개의 동전으로는 기존에 만들 수 있던 1원, 2원에다가 3원을 더할 수 있으므로 3, 4, 5원이 만들어지므로 answer = 6이 된다(answer += 3). 이런 식으로 최고금액을 갱신하여 만들 수 없는 금액을 찾았을 때 반복을 종료하면 된다.

# solution 2 ★★★
# 화폐 단위가 작은 것부터(오름차순) 만들 수 있는 (최고)금액을 갱신해 나가는 것
# 1부터 answer -1 까지의 모든 금액을 만들 수 있는지 확인
n = int(input())
coin = list(map(int, input().split()))
coin.sort()

answer = 1
for x in coin:
    # 만들 수 없는 금액을 찾았을 때 반복 종료
    if answer < x:
        break
    answer += x
print(answer)

2️⃣ 볼링공 고르기 (2019 SW 마에스트로 입학 테스트)

새로 알게된 파이썬 문법은 길이가 정해진 리스트의 선언이다. [0 for _ in range(n)] 형식을 많이 썼었는데 [0] * n 방법이 된다.. 무게가 i인 볼링공의 개수와 경우의 수를 곱할 수 있다.

n, m = map(int, input().split())
data = list(map(int, input().split()))
weight = [0] * 10  # [0 for _ in range(m)]과 같은 표현
for i in data:
    weight[i - 1] += 1
answer = 0
for i in range(m):
    n -= weight[i] #무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    answer += weight[i] * n #B가 선택하는 경우의 수와 곱하기
print(answer)

3️⃣ 무지의 먹방 라이브 (2019 카카오 신입 공채)

문제 바로가기(프로그래머스)

최소 k // n 번의 사이클을 돌아야 가능한 문제라고 생각했는데 코드 돌려보니 정확도는 다 맞았지만 효율성테스트에서 걸렸다. 한번 복잡하게 생각하니까 계속 꼬였는데.. 암튼 결론적으로 우선순위큐(최소힙)을 사용해 쉽게 해결할 수 있는 문제였다. 모든 음식을 시간을 기준으로 정렬하여 시간이 적게 걸리는 음식부터 제거해 (그 시간만큼 사이클을 돌린다고 생각) 구현하면 된다.

파이썬의 힙 자료구조는 heapq(priority queue) 내장 모듈이다. 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식원소들(2k+1, 2k+2)보다 작거나 같은 최소 힙의 형태로 정렬된다.

• heapq.heappush(heapName, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 힙이 비어있는 경우 IndexError 호출됨.
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (선형시간 내에, O(N))

# solution 4
# 우선순위 큐(최소힙) 이용한 방법
# 모든 음식을 우선순위 큐에 (음식 시간, 음식 번호) 형태로 삽입한다
# k 값에서 먹은 시간을 빼는 방법
import heapq

def solution(food_times, k):
    #전체 음식을 먹는 시간보다 k가 크거나 같다면 -1
    if sum(food_times) <= k:
        return -1

    #시간이 작은 음식부터 빼야 하므로 우선순위 큐 이용
    q = []
    n = len(food_times)
    for i in range(n):
        heapq.heappush(q, (food_times[i], i + 1)) #(음식시간, 음식번호) 형태로 삽입
        
    #사이클 돌면서 k에서 (사이클길이(len) * 최소음식시간)을 빼준다
    previous = 0 #직전에 다 먹은 음식 시간
    while (q[0][0] - previous) * n <= k:
        k -= (q[0][0] - previous) * n
        previous = heapq.heappop(q)[0]
        n -= 1
    q.sort(key=lambda x: x[1]) #음식번호 기준 정렬
    answer = q[k % n][1]
    return answer