[이코테] 그리디(Greedy)

참고자료: 이것이 코딩 테스트다 with 파이썬

 

그리디 (Greedy)

💡 현재 상황에서 지금 당장 좋은 것만 고르는 방법 → 탐욕법

 

예제 - 거스름돈

n = 1260
count = 0
	
coin_types = [500,100,50,10]
	
for coin in coin_types:
	count += n // coin
	n %= coin
	    
print(count)

✔ 가장 큰 화폐 단위부터 돈을 거슬러 주는 것

 

 

큰 수의 법칙

n, m, k = map(int, input().split())
data = list(map(int, input().split()))

data.sort()

first = data[n-1]
second = data[n-2]

result = 0

while True:
    for i in range(k):
        if m == 0:
            break
        result += first
        m -= 1
    if m == 0:
        break

    result += second
    m -= 1

print(result)

✔ 입력값 중에서 가장 큰 수와 두 번째로 큰 수만 저장

 

 

숫자 카드 게임

• min() 함수를 이용

n, m = map(int, input().split())
min_list = [] //min_list를 사용해서 작은 수들 넣고 가장 큰 수 print

for i in range(n):
    data = list(map(int, input().split()))
    min_list.append(min(data))

print(max(min_list))

# 교재 풀이
n, m = map(int, input().split())
result = 0

for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    #'가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result)

 

1이 될 때까지

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

count = 0

while n >= k:
    while n % k != 0:
        n -= 1
        count += 1

    n //= k
    count += 1

while n > 1:
    n -= 1
    count += 1

print(count)

✔ 최대한 많이 나누기를 수행