친구가 석박통합 대학원과정을 합격해서 공부하던 코테 책을 넘겨주었다.
이것이 코딩테스트라는 책인데 책도 받은기념 책으로 공부하는거 기록하기..
그리디(Greedy) 알고리즘은 단순하지만 강력한 문제해결 방법이라고 한다. aka 탐욕법
현재 상황에서 지금당장 좋은것만 고르는 방법
현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
'가장 큰 순서대로' / '가장 작은 순서대로' 와같은 기준을 알게 모르게 제시해주는 문제가 많다고 한다. 특히 '정렬'문제와 짝으로 많이나온다고 한다.
문제 : 당신은 점원이다. 거스름돈 500원, 100원, 50원, 10원짜리 동전이 무한. 거슬러줘야할 돈이 N원일때 거슬러 줘야할 동전의 '최소 개수'를 구하라 but 거슬러 줘야할 돈 N은 항상 10의 배수
해설 - 가장 대표적인 그리디 알고리즘 문제! '가장 큰 화폐 단위'부터 거슬러 줄 수 있을 만큼 거슬러주면 된다.
n = int(input())
count = 0
coin_types = [500,100,50,10]
for coin in coin_types:
count += n // coin
n % =coin
print(count)
coin_types 리스트에는 큰 동전부터 작성한다.
시간 복잡도는 동전의 종류를 K개라고 하면 O(K)이다.
그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한 해법인지 검토해야 한다고 한다. 거스름돈 문제에서는 가지고 있는 동전에서 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다!!
예시로 800원 을 거슬러 줄때 거스름돈의 단위가 500원 400원 100원이면 최적의 솔루션은 400원 짜리를 2개 거슬러주는거다.
대부분의 그리디 알고리즘 문제에서는 위처럼 아이디어를 떠올려보고 이것이 정당한지 검토할수 있어야된다고 한다!
동빈이의 큰수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단 배열의 특정한 index에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없는 것이 이법칙의 특징이다.
2,4,5,4,6으로 이루어진 배열이 있을때 M이 8이고 K가 3이라고 하면 같은 인덱스가 3번까지 더해질수 있으니깐 6+6+6+5+6+6+6+5 인 46이 된다.
서로 index가 다르면 다른것으로 간주
입력예시
5 8 3
2 4 5 4 6
출력 예시 - 46
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)
위처럼 입력을 받아줘서 입력값중에서 제일 큰수와 작은수를 받아서 k번 더해준다.
하지만 위의 방식으로 하면 M의 크기가 100억이상으로 커지면(흐음...) 시간초과를 받는다고 한다.
여기서 가정을 N이 5 이고 입력값이 2,4,5,4,6 일때
가장큰수는 6이고 두번째로 큰수는 5이다.
이때 M =8, K=3 이면 (6+6+6+5)+(6+6+6+5)로 정답이 46이된다.
이를보면 가장큰수와 두번쨰로 큰수가 더해질 때는 특정한 수열 형태로 반복해서 더해지는데 이때 수열의 길이는 M/(k+1)로 나눈 몫이 수열의 반복횟수가 된다.
k+1로 나누어 떨어지지 않으면 나머지만큼 가장큰 수가 추가로 더해진다.
이를 공식으로 하면 int(M /(k+1)) * K+M%(K+1)
count = int(m/(k+1)) *k
count +=m%(k+1)
result =0
result += count * first
result += (m-count)* second
로 효율적으로 풀수있다고 한다.
간단했던 문제!