당장 좋은 것만 선택하는 그리디
'탐욕법' 이라고도 하여서 현재 상황에서 당장 좋은 것만 고르는 방법을 의미한다.사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형
연습문제
1. 거스름돈
가장 큰 화폐단위부터 돈을 거슬러주기
N = int(input("거스름돈 입력: "))
coins = [500, 100, 50, 10]
cnt = 0
for coin in coins:
cnt += N // coin
N %= coin
print("동전의 최고 개수는 ", cnt, "개 입니다")2. 큰 수의 법칙
가장큰수 K개와 두번째로 큰수 한개를 하나의 묶음으로 생각해보자
# 가장큰수 a와 두번째로 큰수 b를 구해서 (a*K+b)를 한세트로 M/(K+1)번 더하고 나머지는 a만큼 더한다.
# 입력받은 N, M, K를 입력받는다.
N, M, K = map(int, input().split())
# 리스트를 입력받는다.
numbers = list(map(int, input().split()))
# 리스트 정렬하기
numbers.sort()
print(numbers)
# 가장수 a와 두번째로 수 b를 구한다.
a = numbers[N-1]
b = numbers[N-2]
# (a*K+b)를 한세트로 M/(K+1)번 더하고 나지는 a만 더한다.
answer = (a*K+b)*(M//(K+1))+a*(M%(K+1))
print(answer)3. 숫자 카드 게임
각 행별로 가장 작은 숫자를 찾은 다음 그중에서 가장 큰 숫자를 찾기
# 각 행의 가장 작은 숫자를 찾고 그중에서 가장 큰 숫자를 가진 행을 찾기
# n, m 입력받기
n, m = map(int, input().split())
# n번 m번씩 숫자입력받기
max_val = 0
for i in range(1, n+1):
row = list(map(int, input().split()))
min_val = min(row)
if min_val > max_val:
max_val = min_val
print(max_val)4. 1이 될때까지
최대한 많이 나누는 것이 이득이다
# 최대한 많이 나누는 것이 무조건 이득
# n, k = map(int, input().split())
# cnt = 0
# while n != 1:
# if n % k == 0:
# n /= k
# else:
# n -= 1
# cnt += 1
# print(cnt)
# 이랬을 때 문제점은 n이 k보다 작아졌을 때 0이 될 수 있다는 것!! 따라서 n이 k이상일때까지만 반복문 돌리기
n, k = map(int, input().split())
cnt = 0
while n >= k:
if n % k == 0:
n /= k
else:
n -= 1
cnt += 1
print(cnt)실전문제
1. 모험가 길드
공포도를 기준으로 오름차순 정렬해서 낮은 사람부터 그룹에 넣고 보내버리기
# 공포도를 기준으로 오름차순 정렬해서 낮은 사람부터 그룹에 넣고 보내버리기
n = int(input())
data = list(map(int, input().split()))
# data 오름차순 정렬
data.sort()
# 우선 결과는 0부터
result = 0
# 여기에 담아보기
group = []
for d in data:
group.append(d)
# 가장 큰 공포도가 모임인원수보다 작으면 결과 올리고 그룹 비우기
if max(group) <= len(group):
result += 1
group = []
print(result)2. 곱하기 혹은 더하기
1과 0인경우에는 더하는 것이 이득이고 나머지는 곱하는 것이 이득이다
# 0이면 더하고 나머지는 다 곱하면 될듯
s = input("문자열 입력 => ")
result = 0
for i in s:
number = int(i)
if result <= 1 or number <= 1:
result += number
else:
result *= number
print(result)
# 놓친부분 : 1인경우에도 곱하는 것보다는 더하는것이 이득임3. 문자열 뒤집기
0인애들, 1인애들 쭉쭉 갯수세서 더 작은 횟수쪽을 가져가면 최소 횟수가 될것
# 0인애들, 1인애들 쭉쭉 갯수세서 더 작은 횟수쪽을 가져가면 최소 횟수가 될것
s = input()
zero_num = 0
one_num = 0
current_num = s[0]
if current_num == '0':
zero_num += 1
else:
one_num += 1
for i in range(1, len(s)):
if current_num == s[i]:
continue
else:
current_num = s[i]
if current_num == '0':
zero_num += 1
else:
one_num += 1
print(min(zero_num, one_num))4. 만들 수 없는 금액
동전들 정렬해서 돌린다음 현재 동전이 target된 금액보다 크면 그 금액은 만들 수 없다.
n = int(input())
coins = list(map(int, input().split()))
# 정렬하기
coins.sort()
target = 1
for coin in coins:
if coin > target:
break
target += coin
print(target)5. 볼링공 고르기
전체경우의 수에서 중복되는 경우의 수를 빼보자
n, m = map(int, input().split())
data = list(map(int, input().split()))
dict = {}
# 전체 경우의 수에서 공통되는 경우를 빼보자
for d in data:
if dict.get(d) == None:
dict[d] = 1
else:
dict[d] += 1
temp = 0
for k, v in dict.items():
if v >= 2:
temp += v * (v - 1) // 2
answer = n * (n - 1) // 2 - temp
print(answer)6. 무지의 먹방 라이브
처음 풀었을 때는 순서대로 시뮬레이션을 돌려봤는데 이렇게 풀면 시간초과에 걸리게 된다. 따라서
1. 음식시간, 음식번호로 묶어서 음식시간을 기준으로 먼저 오름차순 정렬을 한다음에
2.음식시간이 가장 작은 녀석부터 k초 안에 다 먹을 수 있는지 검사해서 다 먹을 수 있으면 빼는 형식으로 하고
3. 이후에 남는 시간은 먼저 음식번호로 재정렬 한다음에
4. 남은 음식개수에서 나머지를 구해서 인덱싱하면 구할 수 있다.
# 첫번째 풀이 : 전체 시뮬레이션 돌려보기
def solution(food_times, k):
answer = 0
# k초동안 다 먹을 수 있으면 바로 -1 리턴
if sum(food_times) <= k:
answer = -1
else:
target = 1
# k초 동안 반복해보자
for _ in range(k):
# 현재 음식 한번 먹기
food_times[target - 1] -= 1
target += 1
if target > len(food_times):
target = 1
# 남아있는 음식까지 이동하기
while food_times[target - 1] <= 0:
if target > len(food_times):
target = 1
target += 1
answer = target
return answer# 두번째 풀이 : 가장 작은 음식시간부터 빼보기
from heapq import heappush, heappop
def solution(food_times, k):
# 전체음식보다 초가 이상이면 k시간안에 다 먹을 수 있어서 -1 리턴하기
if sum(food_times) <= k:
return -1
answer = 0
# food_times 기준으로 (음식시간, 인덱스) 형태로 저장하기
heap = []
for i in range(len(food_times)):
heappush(heap, (food_times[i], i + 1))
# 처음 음식갯수 구하기
foods = len(food_times)
# 이전의 걸린 초 구하기
prev = 0
while True:
# 가장 적게 걸리는 녀석 찾기
min_val = heap[0][0]
# 걸리는 시간은 현재 음식 먹는 시간에서 이전 음식시간 빼고나서 음식갯수만큼 곱해서 구하기
during_time = (min_val - prev) * foods
# 다 먹기전에 초가 끝난다면 반복문 나가기
if during_time > k:
break
# 다 먹을 수 있으면 먼저
# 1. 걸린시간 만큼 k에서 빼주기
# 2. 다 먹은 음식 빼기
# 3. 이전먹은 음식을 현재 뺀 음식시간으로 갱신해주기
else:
k -= during_time
heappop(heap)
foods -= 1
prev = min_val
# 뒤의 값인 음식 번호(i+1)로만 오름차순 정렬된 리스트 생성
heap.sort(key=lambda x: x[1])
# 인덱스는 남은 초에서 음식갯수를 빼고나면 k초이후에 먹어야 하는 음식번호이다
idx = k % foods
answer = heap[idx][1]
return answer