455. Assign Cookies

이 문제에서는 어떤 아이들이 존재하며,
각각의 아이들은 만족할 수 있는 최소한의 쿠키 크기를 가지고 있습니다.
또한, 쿠키들도 각각의 크기를 가지고 있습니다.
이 문제에서는 아이들에게 쿠키를 나눠주는 방법을 찾아야 합니다.
이때, 각 아이들은 최대 한 개의 쿠키만 받을 수 있습니다.
따라서, 가능한 많은 아이들에게 쿠키를 나눠주는 방법을 찾아야 합니다.
이 문제는 그리디 알고리즘을 사용하여 해결할 수 있습니다.

public class Solution {
    public int FindContentChildren(int[] g, int[] s) {
        Array.Sort(g);
    	Array.Sort(s);
    	int i = 0;
        for (int j = 0; i < g.Length && j < s.Length; j++) {
            if (g[i] <= s[j]) {
                i++;
            }
        }
        
    return i;
    }
}

입력으로 주어진 g와 s 배열을 오름차순으로 정렬한 후, g와 s 배열의 원소를 비교하여 가능한 많은 아이들에게 쿠키를 나눠주는 방법을 찾습니다.

이 코드에서는 i와 j 변수를 사용하여 g와 s 배열의 원소를 비교합니다. i는 g 배열의 인덱스를, j는 s 배열의 인덱스를 나타냅니다. i와 j를 0으로 초기화한 후, g[i]와 s[j]를 비교합니다. 만약 g[i]가 s[j]보다 작거나 같으면, i를 1 증가시킵니다. 이렇게 하면 g 배열의 다음 원소와 s 배열의 다음 원소를 비교할 수 있습니다. 이 과정을 g 배열의 모든 원소와 s 배열의 모든 원소를 비교할 때까지 반복합니다.

최종적으로, i 변수의 값을 반환합니다. 이 값은 가능한 많은 아이들에게 쿠키를 나눠줄 수 있는 최대 개수입니다.

---

그리디 알고리즘(Greedy algorithm)은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여
러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달합니다. 이 알고리즘은 일반적으로 간단하고 빠르며, 최적해를 구하는 데에 사용됩니다.
그러나, 이 알고리즘이 항상 최적해를 구할 수 있는 것은 아니며,
경우에 따라서는 근사적인 해답만을 구할 수 있습니다 

using System;

class Program
{
    static int MinCoins(int[] coins, int amount)
    {
        Array.Sort(coins);
        Array.Reverse(coins);
        int count = 0;
        foreach (int coin in coins)
        {
            if (amount == 0)
            {
                break;
            }
            count += amount / coin;
            amount %= coin;
        }
        return count;
    }

    static void Main(string[] args)
    {
        int[] coins = { 1, 2, 5, 10, 20, 50, 100, 500, 1000 };
        int amount = 93;
        Console.WriteLine($"Minimum number of coins required to make {amount} is {MinCoins(coins, amount)}");
    }
}