현재 상황에서 지금 당장 좋은 것만 고르는 방법으로
그리디 알고리즘은 가장 큰 값만 고른다. (탐욕법)
1.거스름돈
<문제 해결 아이디어>
1. 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 준다.
-> 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위들의 동전을 종합해 다른 해가 나올 수 없다.
큰 단위가 작은 단위의 배수가 아니라면 최적의 해가 나오지 않는다.
2. n원을 거슬러 줘야 할때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. (이후 100, 50, 10원~)
<코드>
n = 1260 #거슬러줄 돈
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기 (리스트에 담기)
coin_types = [500, 100, 50, 10]
for coin in coin_types: #각각의 동전확인 : for in으로 coin_types(리스트)의 모든 내용을 coin이라는 변수에 담는다.
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기 2 += 1260//500
n %= coin # 거슬러준 다음 260원 남은걸 n에 넣기 (%=나머지)
print(count)
#결과 : 6"""
결과값(count)에 n을 코인으로 나눈 몫(//)을 담는다.
현재 남아있는 <돈=n>을, 현재 <coin>으로 최대한 많이 거슬러 줄 수 있도록 하고, 그 거스름돈의 개수를 더해준다.
이후 남은 돈은 coin보다 더 작아져야 하므로, n을 coin으로 나눈 나머지 값이 될 수 있도록
1260원을 500원으로 2번 거슬러주면, 260원이 남는다.
260원을 100원으로 나누면
260을 200으로 나눈 나머지인 60이 남는다.
화폐의 종류만큼 반복이 수행
"""
<시간복잡도>
- 화폐의 종류가 K라고 할때, 코드의 시간 복잡도는 O(K)
- 이 알고리즘의 시간복잡도는 거슬러줘야하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.
2.1이 될때까지
<문제>
<조건>
<문제 해결 아이디어>
주어진 N에 대하여 최대한 많이 나누기 -> 최적의 해 보장 (N이 아무리 큰 수여도 K로 나눈다면 빠르게 줄어든다.)
<코드>
#N, K을 공백을 기준으로 구분하여 입력받기
n, k = map(int, input().split()) # 25,3 입력
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지 빼기
target = (n//k) * k
result += (n - target)
n = target
# N이 K보다 작을 때(더이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# K로 나누기
result += 1
n //= k
#n이 1보다 크다면 1로 만들기 위해서, 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)
#실행결과 : 6
"""
풀이
n==25 ,k==3
<While>
-첫번째 반복-
target = (8) * 3
-> target : k로 나누어 떨어지는 수
n이 k로 나누어 떨어지지 않을때, 가장 가까운 나누어 떨어지는 수 찾을 수 있음
result += 25-24
n = 24
-> result : 총 연산을 수행하는 횟수, 1을 빼는 연산을 몇번 수행할지, n을 타겟으로 만든다
result==2
24 //=3
-> n==8
-두번째 반복-
target = (8//3) * 3 ->6
result += (8-6) ->2
n=6
result =3
6 //=3
-> n==2
-세번째 반복-
target = 0
result =4
n==0
result==5
print
result ==6
"""
3.최고의 피자
<문제>
<입력>
<해결>
-> (칼로리 / 가격)
1.토핑 칼로리 내림차순 정렬(열량 높게 나오기 위해서 높은 순으로)
2.토핑개수만큼 반복하며 피자칼로리 계산
n= int(input()) #토핑 종류 수
a,b =map(int,input().split()) #도우,토핑 가격
c =int(input()) #도우 칼로리
#토핑 칼로리 리스트
toping = []
#토핑 칼로리를 토핑 종류 수의 개수만큼 입력받기
for _ in range(n):
toping.append(int(input()))
#내림차순(칼로리 큰 순서로 정렬)
toping.sort(reverse=True)
result = c / a #현재는 도우만 있는것이 최고의 피자 : 도우의 1달러당 칼로리 :칼로리/달러
#토핑개수만큼 반복
for i in range(1, len(toping)+1):
calorie = c + sum(toping[0:i]) #칼로리 : 도우 +(토핑칼로리sum)
price = a + (b * i) #가격
if calorie / price > result: #토핑 추가한 것 > 도우만 있는것
result = calorie / price #결과 값 바꾸기
else:
break #도우의 칼로리가 제일 높으면 종료 하고 출력(토핑 없어도 되니까)
print(int(result)) #정수로 출력
문제 : https://codeup.kr/problem.php?id=3321&rid=0
참고 : https://jokerldg.github.io/algorithm/2021/07/08/best-pizza-store.html
4.곱하기 혹은 더하기
<문제>
최대값 주어지는 이유
-> 정수데이터를 위해 int형 사용할 경우 약 21억정도 형성될 수 있기 때문에
(파이썬은 수의 범위에 제한이 없어서 괜찮다.)
<조건>
<문제해결 아이디어>
- 대부분의 경우 + 보다는 x가 값을 더 크게 만든다.
- 다만 두 수 중 하나라도 0이나 1일 경우 곱하기 보다는 더하기를 하는 것이 효율적
- 따라서 두 수에 대하여 연산을 수행할때 두 수 중 하나라도 1이하인 경우 더하기,
두 수 모두 2이상인 경우 곱하기를 하면 정답
- 현재상태에서 조건이 맞다면 더하기를 수행하고 아니면 곱하기를 수행하는 것은 전형적인 그리디 알고리즘이다.
<코드>
data = input()
#첫번째 문자를 숫자로 변경하여 대입
result = int(data[0])
for i in range(1, len(data)):
#두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
num =int(data[i])
if num <=1 or result <=1:
result += num
else:
result *= num
print(result)
"""
입력 : 123
결과 : 9
"""5.최소대금
https://codeup.kr/problem.php?id=2001
pasta = [] #리스트로 입력받기
for i in range(3) : #3종류파스타
pasta.append(float(input())) #실수로 입력받기
juice = []
for i in range(2) :
juice.append(float(input()))
"""
1.정렬로 접근
pasta = sorted(pasta)
juice = sorted(juice)
print(round(((pasta[0]+juice[0])*1.1),1)) #소수점 첫번째 자리 출력
"""
#2.min으로 접근
result=(min(pasta) +min(juice)) + ((min(pasta) +min(juice))*0.1) #파스타와 생과일 쥬스의 가격 합계에 10%를 더한 금액
print(format(result,".1f")) #소수점
6.모험가 길드
<문제>
N < X 여야 모험 가능
<조건>
<문제 해결 아이디어>
<코드>
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0 # 총 그룹의 수
count = 0 # 현재 그룹에 포함된 모험가의 수
for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
count += 1 # 현재 그룹에 해당 모험가를 포함시키기
if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
result += 1 # 총 그룹의 수 증가시키기
count = 0 # 현재 그룹에 포함된 모험가의 수 초기화
print(result) # 총 그룹의 수 출력
"""
입력 :
5
1 2 3
출력 : 1
강의 : https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5
댓글