그리디(탐욕) 알고리즘

 

현재 상황에서 가장 좋은 것만 고르는 욕심꾸러기!

 

정당성 분석이 가장 중요.

 

가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

 

ex.

동전 거슬러줄 때, 단위가 큰 동전부터 생각해야 하는 이유?

큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문.

 

coins = [500, 100, 50, 10]
pocket = int(input("얼마있어?\n"))
count = 0
answer = {}

for coin in coins:
  count += pocket // coin
  answer[coin] = pocket // coin
  pocket %= coin

print(answer)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner userInput = new Scanner(System.in);
        System.out.println("얼마있어?");
        int n = userInput.nextInt();
        int cnt = 0;
        int[] coinTypes = {500, 100, 50, 10};
		
        for (int i = 0; i < 4; i++) {
            int coin = coinTypes[i];
            cnt += n / coin;
            n %= coin;
        }

        System.out.println(cnt);
        userInput.close();
    }

}

 

총 금액이 아닌, 동전의 종류 수에만 영향을 받는 O(n)

 

 

n, k = map(int, input().split())
print(n, k)

count = 0

while(n != 1):
  if n % k == 0:
    n /= k
  else:
    n -= 1
  count += 1

print(f"n: {n} k: {k} count: {count}")

곱하거나 더해서 가장 큰 수 만들기 : 두 수 중 하나라도 1 이하이면 더하고, 두 수 모두 2 이상이면 곱한다.

data = input()
prev = int(data[0])

for i in range(1, len(data)):
  next = int(data[i])
  if prev <= 1 or next <= 1:
    prev += next
  else:
    prev *= next

print(prev)