[アルゴリズム]GRADYアルゴリズム?

グリディアルゴリズム!
以前は学校のアルゴリズムの授業(教授の授業が大好きで、勉強しないで冷遇されていました)で「Gredy」アルゴリズムという言葉を聞いた後、名前が独特でした...と思った.
名前の値(?)アルゴリズムです...
その时、私は努力して勉強すると思いますが、もう一度精読して、テープを用意します.

1.グリディアルゴリズムとは?

Greedyアルゴリズム?

現在の状況では、すぐに良いものを選ぶ方法

「最大の順序に従う」「最小の順序に従う」などの基準.

単純に暗記して、解題方法を知っているので、簡単なタイプではありません.
最も重要なのは問題を解決する最低限の考えを考え出す能力です!

2.代表例

小銭の問題
時間複雑度O(N):通貨種別別

n = 1260 # 거스름돈
cnt = 0

coins = [500, 100, 50, 10]

# 동전의 종류를 순회하면서 체크한다
for coin in coins:
    cnt += n // coin
    n %= coin # 나머지 거스름돈

print(cnt)

3.グリディアルゴリズムが実行できる理由?

2つ目の小銭問題がグリディで解決できるのは、大きな単位の硬貨がいつも小さい単位の硬貨の倍数であるからだ.
→どういう意味ですか?
500元は100,50,10の倍数、100元は50,10の倍数、50元は10の倍数...
小さい単位の硬貨を集めて、最終的に大きい単位の硬貨になって、お金を探す時一回大きいのにあげて、最終的に硬貨を少なくします!
学習源:これは就職のために行われたコードテストです.董文娜