문제

https://www.acmicpc.net/problem/10162

문제 접근

가장 적은 횟수로 시간을 채우라는 문제이다. 역시 그리디로 접근할 수 있다.

코드

t= int(input())

times = [300,60,10]
result = list()

for time in times:
    if t//time > 0:
        result.append(t//time)
        t = t%time
    else:
        result.append(0)
        
for r in result:
    if t == 0:
        print(r, end=' ')
    else:
        print(-1)
        break

배운점

그리디 문제는 리스트과 정렬!

문제

https://www.acmicpc.net/problem/5585

문제 접근

큰 돈부터 거슬러 준다. 그리디다.

코드

n = int(input())

coins = [500,100,50,10,5,1]
r = 1000-n
count =0
for coin in coins:
    if r//coin > 0:
        count += r//coin
        r = r%coin

print(count)

배운점

이제 암기해라. 이런 느낌의 그리디 문제는 배열과 정렬이다!

문제

https://www.acmicpc.net/problem/1026

문제 접근

가장 작은 값을 만들기 위해서는 (a 배열에서 가장 큰 값 * b 배열에서 가장 작은 값) 에서 (a 배열에서 가장 작은 값 * b 배열에서 가장 큰 값) 의 형태로 더해줘야지 최솟값이 나오게 된다. 즉, 그리디를 사용하자!

코드

n = int(input())

a = list(map(int,input().split()))
b = list(map(int,input().split()))

a.sort()
b.sort(reverse = True)

sum = 0
for i in range(0,n):
    sum += a[i]*b[i]

print(sum)

배운점

쉬운 그리디 문제는 보통 리스트와 그에 대한 정렬을 이용해서 많이 풀 수 있다는 것을 느낄 수 있었다.

문제

https://www.acmicpc.net/problem/11399

문제 접근

 최소의 시간이 걸리기 위해서는 결국 시간이 적게 드는 것 부터 처리해야 하므로 그리디 알고리즘은 적용해서 문제를 풀었다.

코드

n = int(input())

time = list(map(int,input().split()))

time.sort()
num = 0
sum = 0

for t in time:
    num = num + t
    sum = sum + num
print(sum)

배운점

이제까지 그리디 알고리즘 문제 2문제를 접해봤지만 공통점이 입력값을 리스트 형태로 받고 정렬하여 하나씩 접근하는 것이였다. 그리디 알고리즘의 한 유형인 것 같다. 

문제

https://www.acmicpc.net/problem/11047

문제 접근

그리디 알고리즘을 적용해 문제를 풀었다. 결국 큰 액수의 돈부터 사용해야 동전의 개수가 최솟값이 되므로 큰 값부터 접근해보자.

예를 들어 보자.

100원 500원 1000원 짜리 동전이 있고 1200원을 만들기 위해서는 1000원 1개, 500원 0개, 100원 2개로 총 3개의 동전이 최솟값이 된다. 

그대로 코드에 적용해보자.

코드

n,k = map(int,input().split())

coins = list()

for i in range(n):
    a = int(input())
    coins.append(a)

# 그리디하게 접근하기 위해 내림차순으로 리스트 정렬
coins.sort(reverse=True)

count = 0

for coin in coins:
    if k >= coin:
        count += k//coin
        k = k%coin

print(count)

배운점

1. 파이썬에서 내림차순으로 정렬하기 위해 sort(reverse=True) 처럼 사용 가능하다. 이런 사소한 것 까먹기 좋은 것 같다.

그리디 알고리즘

Greedy : 탐욕스러운 이라는 뜻을 가진다. 

즉, 그리디 알고리즘은 탐욕스럽게 현재 상황에서 가장 이익이 되는 것을 고르는 방법이다. 

대표적인 예가 조삼모사 라고 생각한다. 뜻과는 반대이지만 우리는 총 7개 중에 아침에 3개를 받을 것이냐 4개를 받을 것이냐 라는 질문에 그리디 알고리즘을 적용한다면 아침에 4개, 저녁에 3개를 선택하게 되는 것이다. 알고 있는 몇 안되는 사자성이다... 

그래서 어떻게 적용해서 문제를 풀거냐? 백준을 풀어보면서 예를 들겠다.

https://codingjobrice.tistory.com/146

https://codingjobrice.tistory.com/145