[알고리즘] Greedy (탐욕법) - 백준 10162 11399 1541 1931 1715

그리디 알고리즘에 대해 공부해보자.

Greedy = 탐욕 = 현재 상황에서 가장 좋은 것만을 선택하는 방법

 

 

그리디 예시 - 거스름돈

 

거스름돈을 거슬러 줄 때 최소 동전(지폐 포함) 개수를 구하는 방법 = '가장 큰 화폐 단위' 부터 거슬러주는 방법이다.

어떻게 구현할 수 있을까?

changes = 14570	# 거스름돈
count = 0	# 거스름돈 화폐 개수
 
money_types = [10000, 5000, 1000, 500, 100, 50, 10]	
 
for money in money_types:
	count += changes // money
    changes %= money
    
print(count)

 

그리디 문제점

현재 상황에서 가장 좋은 것 = 전체 상황에서 가장 좋은 것?아니다.

 

부분 최적해는 구할 수 있지만 전체 최적해는 구할 수 없는 경우가 존재한다.

 

 

그리디 문제풀이

백준 사이트에 올라온 그리디 문제들을 풀어보자. 코딩 실력이 아직 부족한 관계로 쉬운 문제들 위주다.

 

10162 전자레인지

 

A 5분, B 1분, C 10초로 최소로 버튼을 눌러 지정된 시간 맞추기, 못 맞추는 시간 단위면 -1 출력

 

t = int(input())
 
a = 300
b = 60
c = 10
ans = []
 
ans.append(t//a)
t %= a
ans.append(t//b)
t %= b
ans.append(t//c)
 
if t % c != 0:
    print(-1)
else:
    for x in ans:
        print(x, end = " ")

 

그리디의 정석이 아닐까 싶은 문제다. 차근차근 내려오면서 풀면 된다.

 

 

11399 ATM

 

사람 N명, i번째 사람이 돈 인출 시 걸리는 시간 Pi분, 인출하는 시간 총 합의 최솟값?

import sys
n = int(input())
 
p = list(map(int, sys.stdin.readline().split()))
 
p = sorted(p)
ans = 0
for i in range(len(p)):
    ans += sum(p[:i+1])
    
print(ans)

 

1541 잃어버린 괄호

문자열 입력받고 적절한 곳에 괄호 넣어서 최솟값 만들기

s = input()
 
sic = s.split('-')
num = []
for x in sic:
    tmp = 0
    el = x.split('+')
    for i in el:
        tmp += int(i)
    num.append(tmp)   
 
n = num[0]
for j in range(1, len(num)):
    n -= num[j]
 
print(n)

 

1931 회의실 배정

시작 시간 / 끝 시간이 주어지면 진행 가능한 최대 회의의 개수 찾기

n = int(input())
 
meet = []
for i in range(n):
    time = list(map(int, input().split()))
    meet.append(time)
 
meet = sorted(meet, key = lambda x : [x[1],x[0]])
 
cnt = 1
tmp = meet[0][1]
for  i in range(1, len(meet)):
    if tmp <= meet[i][0]:
        cnt += 1
        tmp = meet[i][1]
 
print(cnt)

람다식좀 잘 알아두면 좋을 것 같다 맨날 생각은 하면서 잘 안쓰게 된다

 

1715 카드 정렬하기

 

처음엔 그냥 소트해서  풀면 될 줄 알았는데 자꾸 출력 초과같은게 떠서 검색해보니까

힙을 쓰는거였다.

자료구조에 좀 더 익숙해져야 한다

"""
n = int(input())
 
cards = []
 
for i in range(n):
    cards.append(int(input()))
    
cards = sorted(cards)
 
tmp = cards[0]
compare = 0
for j in range(1, len(cards)):
    compare += tmp + cards[j]
    tmp = compare
    
print(compare)
 
"""
 
import sys
import heapq
 
 
n = int(sys.stdin.readline())
cards = []
for _ in range(n):
    heapq.heappush(cards, int(sys.stdin.readline()))
 
if len(cards) == 1:
    print(0)
else:
    ans = 0
    while len(cards) > 1:
        tmp1 = heapq.heappop(cards)
        tmp2 = heapq.heappop(cards)
        ans += tmp1 + tmp2
        heapq.heappush(cards, tmp1 + tmp2)
    print(ans)