알고리즘-그리디1

친구가 석박통합 대학원과정을 합격해서 공부하던 코테 책을 넘겨주었다.

이것이 코딩테스트라는 책인데 책도 받은기념 책으로 공부하는거 기록하기..

그리디 - 당장 좋은 것만 선택하는 알고리즘

그리디(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 

로 효율적으로 풀수있다고 한다.

간단했던 문제!