알고리즘 정리에 중점을 둔 글이기 때문에
책 초반에 나와있는 실습환경 구축 같은 내용은 생략하고 곧바로 그리디(Greedy)알고리즘 부터 시작하도록 한다.
그리디란?
현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘
📄 많은 유형을 접해보고 풀어보는 것이 그리디 알고리즘 유형을 대처하는 가장 좋은 방법
📄 코테를 풀고 있는데 문제 파악이 잘 안되는 경우, 그리디 알고리즘으로 접근해보도록 하자.
📄 문제 풀이의 방식이 정당한지 검토할 수 있어야 한다.
그리디 예제문제
예제 1) 거스름돈
(*500원, 100원, 50원, 10원의 동전이 무한히 존재한다고 가정)
손님에게 거슬러줘야하는 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수는? (N은 항상 10의 배수)
=> '최소' 개수니까 큰 단위부터 차근차근 없애는게 좋지 않을까?
=> 500원 -> 100원 -> 50원 -> 10원 순으로 거슬러준다.
ex) N=1260
500 : 2
=> 1260-(500x2)=260
100 : 2
=> 260-(100x2)=60
50 : 1
=> 60-(50x1)=10
10 : 1
=> 10-(10x1)=0
500원 2개, 100원 2개, 50원 1개, 10원 1개 이므로 최소개수는 총 6개
이를 바탕으로 코드 작성을 해보도록 한다.
👇 답지를 보기 전 작성한 코드
N=int(input()) # 남은 돈
n=0
while N//500>0:
N-=500
n+=1
while N//100>0:
N-=100
n+=1
while N//50>0:
N-=50
n+=1
while N!=0:
N-=10
n+=1
print(n) # 최소 동전 개수 답안 예시를 본 후의 피드백
ⓐ 굳이 while문을 쓰지않고 for문을 통해 간단하게 줄일 수 있었음
ⓑ 500, 100, 50, 10원 단위를 리스트로 미리 작성해서 묶어놓으면 더 편리했음
👇 피드백 후 코드
N=int(input())
coin_types=[500,100,50,10]
count=0
for coin in coin_types:
count+=N//coin
N%=coin
print(count)그리디 실전문제
1) 큰수의 법칙
주어진 수들을 N번 더하여 가장 큰 수를 만들어냄
단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 계산 M번을 초과할 수 없음
(*단, 다른 인덱스 같은 숫자는 서로 다른것으로 간주)
배열의 크기, 숫자가 더해지는 횟수 N, M이 주어졌을 때의 결과는?
👇 답지를 보기 전 작성한 코드
size,N,M=list(map(int, input().split())) # 배열의 크기, 더하는 횟수,최대 횟수
x=list(map(int, input().split()))
x.sort()
x_max=x[-1]
x_second_max=x[-2]
answer=0
count=0
while N!=0:
if count==M:
answer+=x_second_max
count=0
N-=1
else:
answer+=x_max
count+=1
N-=1
print(answer)답안 예시를 본 후의 피드백
ⓐ 제일 큰 수와, 두 번째로 작은 수를 구해서 계산에 쓴다는 접근은 좋았음
ⓑ 하지만 시간 초과 판정을 받을 수 있는 코드 => 어떻게 하면 시간을 더 줄일 수 있을까?
❗ 반복되는 수열에 대해서 파악을 해야한다 ❗
ⓐ 첫 번째로 큰 수와 두 번째로 큰 수를 더하는 방식이 계속해서 반복될 것임
ⓑ 첫 번째로 큰 수를 중복해서 더하다가 K의 횟수까지 오게 되면 두 번째로 큰 수를 한번 더하고
갱신된 중복 계산 횟수를 토대로 다시 첫 번째로 큰 수를 K번까지 더하는 방식...
ⓒ 그렇다면 같은 수열이 반복되는 것과 같다고 생각
ⓓ 수열의 길이는 (K+1)과 같음
ⓔ 근데 이 때, N으로 인해 중복되던 수열 형태와 다르게 끝날 수 있음
ⓕ ( (K+1)로 나눈 나머지 * 첫 번째로 큰 수) 로 계산하면 됨
👇 피드백 후 코드
n,m,k=list(map(int, input().split())) # 배열의 크기, 더하는 횟수,최대 횟수
x=list(map(int, input().split()))
x.sort()
x_max=x[-1]
x_second_max=x[-2]
answer=0
count=int(m/(k+1))*k #가장 큰 수가 더해지는 계산
count+=m%(k+1)
answer+= count*x_max
answer+=(m-count)*x_second_max
print(answer)
.gif)