그리디 알고리즘

그리디 알고리즘이란?

현재 상황에서 지금 당장 좋은 것만 고리는 방법 = 탐욕적, 욕심쟁이 기법! = GREEDY!
현재상황에서 가장 좋아보이는 것을 선택해도 문제를 풀 수 있나?를 생각했을 때 그것이 성립하다면 GREEDY를 시도할 것!

---

기본적인 예제

1. 거스름돈 문제 => 최소 거스름돈의 개수 => 개수를 적게 만들기 위해서는 당연히 주는 동전의 단위가 커야함.
=> for문을 돌릴때 동전의 단위가 큰 것부터 걸리게끔 조건을 걸고 동전의 나머지가 0이 되는 순간 개수 출력

x = int(input()) cnt = 0 while x!=0: if x//500: print(x//500) cnt = cnt + x//500 x = x%500 if x//100: print(x//100) cnt = cnt + x//100 x = x%100 if x//50: print(x//50) cnt = cnt + x//50 x = x%50 if x//10: print(x//10) cnt = cnt + x//10 x = x%10 print(cnt)

* list(map(int, input().split()))을 통해서 띄어쓰기별로 입력받은 값을 list로 저장할 수 있게 됨.
* 더 간결하게 작성하기 위해서는 500,100,50,10원을 list에 넣어놓고 차례대로 for문을 돌려도 됐음 => if문을 4개로 할 필요가 없어짐.

2. 큰 수의 법칙 => 입력받은 숫자에서 가장 큰 수를 계속 더해주다가 연속 더한 개수가 k개를 초과할 경우 그때는 그 다음의 큰 수를 더해주고 다시 가장 큰 수를 계속더하기를 반복.

#큰수의 법칙 n,m,k = map(int, input().split()) num = list(map(int, input().split())) num.sort() max_list=[] max_list.append(num[n-1]) max_list.append(num[n-2]) #print(max_list) #큰수, 그 다음으로 큰 수가 들어가있음 sum = 0 max_cnt=0 for i in range(0,m): if max_cnt<k: sum = sum+max_list[0] max_cnt = max_cnt+1 else: sum = sum+max_list[1] max_cnt=0 print(sum)

* sort()는 기본적으로 오름차순으로 내림차순 정렬했다면 .sort(reverse = True)로 작성하고 num[0], num[1]을 이용

3. 숫자 카드 게임 => 각 행의 가장 작은 숫자가 각 행을 선택했을 때의 결과이기에, 어떤 행을 선택해야 가장 큰 값을 나오는지 구하는 문제에서는 각 행별로 가장 작은 숫자를 list에 저장하고 배열해서 가장 앞의 값을 뽑아내거나 max를 사용하면 된다고 생각해서 max를 사용함

숫자 카드 게임 -> 가장 작은 수들을 행별로 저장하고 그 저장한 리스트에서 가장 큰 값을 뽑아내면 답 n, m = map(int, input().split()) min_=[] for i in range(n): list_=[] list_=list(map(int, input().split())) min_.append(min(list_)) print(max(min_))

4. 1이 될 때까지 => n에서 1을 빼거나 n을 k로 나누는 두가지 경우중 선택가능하지만 k로 나눌때는 나누어떨어져야 가능함 => 이때, n이 1이 되기 위해 수행해야하는 최소 개수를 구하면 되니까 n이 k로 나누어 떨어진다면 무조건 나누고 그게 아니라면 1을 어쩔 수 없이 빼야함

n,k = map(int, input().split()) sum=0 while n!=1: if n%k==0: n //= k sum += 1 else: n -= 1 sum += 1 print(sum)