グレースケールアルゴリズム

アルゴリズムサークル第3週コース
今回の発表の準備は私です.
発表資料はこれがコードテストの複数の本とCode Eatアルゴリズムの授業であることを参考にした.

コンセプト

符号化テストでグレディアルゴリズムの問題に慌てたくないなら,多くのタイプの問題を解決しようとする必要がある.

グリディアルゴリズムを用いることが良い解決策であるためには,最適部分構造と貪欲な選択属性を満たさなければならない.
貪欲な選択属性は直感的で簡単であるが,最適な部分構造は最初は触れなかった.
最も理解に役立つ例は、道を探すことを例に挙げた問題である.
AからCまでできるだけ速くする必要がある場合、
A~Bの最速路+B~Cの最速路=A~Cの最速路
このように,原問題の一部の問題に対して最良の答えの構造を構成した.
私が理解する方法は、貪欲な選択属性は本来、その後どうなるかを考えず、現在の貪欲な選択だけを選択することですが、最適な部分構造を形成するには、私は最後の段階で最適な選択をしただけで、これが最終的な問題の最適な選択であることを受け入れました.

例1。金をさがす

最も少ないコインを使ってお金を探します:1260元

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n//coin
    n %= coin

print(count)

例2。最大積を求める

質問する
何人かがトランプゲームをしていて、プレイヤー一人一人が3枚のトランプを持っています.
一人一人がカードを1枚引いて、すべての可能な最大乗を乗じます.
方法
1.関数max product:1人1枚のカードを引いて、可能な最大積をすべて乗じたときに返します.
2.欲張りな選択:3枚のカードの中で最大の値を選ぶ

def max_product(card_lists):
    
    product = 1 #곱 저장 변수
    
    for i in card_lists: #플레이어들의 카드 리스트 돌기
        product = product * max(i) # 최댓값을 곱함
    return product

# 테스트
test_cards1 = [[1, 6, 5], [4, 2, 3]]
print(max_product(test_cards1))

test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], [7, 7, 4]]
print(max_product(test_cards2))

例3。1になったとき。

質問する
ある数Nが1になるまで、次の2つのプロセスのいずれかを繰り返し選択します.2つのプロシージャを実行する必要がある回数の最大値を出力します.
NをKで割った場合のみ、2番目の演算を選択できます.
1.Nから1を引く
2.NをKで割る
入力条件:最初の行はNとKをスペースで区切り、それぞれ自然数で与えられます.N>=K
出力条件:1行目Nが1になるまで繰り返す最小回数を出力する.
方法
貪欲な基準:共有は数をより速く小さくし、共有できれば共有し、そうでなければ1を減らす.

n, k = map(int, input().split())
result = 0

# N이 K이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
    while n%k != 0:
        n -=1
        result += 1
    # K로 나누기
    n //= k
    result += 1
# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    result += 1

print(result)

GRADYアルゴリズム推奨問題

白駿11399 1931 2217号.