これはPythonを読んでコードテストを行う文章です.

グリディ

今の状況では、今は良いものだけを選ぶ方法です.

[質問]おつり

500、100、50、10円玉は無限に存在するという.
探しているお金がN元の場合、探しているコインの最低個数を求めます.
しかし、Nは常に10の倍数である.
->最大の通貨単位から、おつりで解決

# 교재 풀이
n = 1260
count = 0

coins_types = [500, 100, 50, 10]

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

print(count)

# 내 풀이
n = int(input())

m = [500, 100, 50, 10]
cnt = 0

for i in m:
    if n == 0:
        break
    cnt += n // i
    n %= i

print(cnt)

通貨種別別繰返し=>時間複雑度O(N)

グリディアルゴリズムの合理性

ほとんどの問題では,グリディアルゴリズムを用いた最適解が見つからない可能性が高い.
そのため、問題解決の最低限の考え方を考え、正当かどうかを検討することができるはずだ.
実際,小銭を探す問題では,硬貨の単位は相互間の倍数形式ではなくランダムに与えられた場合,グリディアルゴリズムでは解決できない.

[問題]大数の法則

この問題の大数の法則は,異なる数の配列がある場合,与えられた数をM回加算して最大数を形成する法則である.
ただし,配列の特定のインデックスの数はK回を連続して超えることはできない.
インデックスによって対応する数が異なる場合も、異なるとみなされます.
この壁値で配列の大きさN,数値加算の回数M,およびKが与えられたときの大数則の結果を出力する.
->重複する数の列を理解します.

# 교재 풀이
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
first = data[n - 1]  # 가장 큰 수
second = data[n - 2]  # 두 번째로 큰 수

count = int(m / (k + 1)) * k
count += m & (k + 1)

result = 0
result = count * first
result += (m - count) * second

print(result)

# 내 풀이
n, m, k = map(int, input().split())
array = list(map(int, input().split()))
array.sort()
f = array[-1]  # 가장 큰 수
s = array[-2]  # 두번째로 큰 수

result = f * (m // k) * k + s * (m % k)

print(result)

[問題]デジタルカードゲーム

数字が書かれたカードがN*Mの形で並んでいます.このときNは行数、Mは列数を表す.
引くカードの行を選択し、その中で最も数字が低いカードを選択します.
多くの場合、一番高い数字のカードを1枚求めます.
->行ごとに最小数を検索し、その中で最大数を検索します.

# 교재 풀이 => 공간효율적
n, m = map(int, input().split())

result = 0
for i in range(n):
        data = list(map(int, input().split()))
        min_value = min(data)
        result = max(result, min_value)

print(result)

n, m = map(int, input().split())

array = []
min_array = []
for i in range(n):
        array.append(list(map(int, input().split())))
        min_array.append(min(array[-1]))

print(max(min_array))

[問題]1まで

任意の数Nが1になるまで、2つのプロセスのうちの1つを繰り返し選択して実行します.
ただし,2番目の演算はNをKで割った場合にのみ選択できる.
1.Nから1を減算します.
2.NをKで割る.
NとKのタイミングでNが1になる前に1回または2回のプロセスを実行する最小回数を求める.
->できるだけ多く分ける.

# 교재 풀이 => 효율적
n, k = map(int, input().split())

result = 0
while True:
    target = (n // k) * k
    result += n - target  # 1번
    n = target

    if n < k:
        break
    result += 1
    n //= k  # 2번

result += (n - 1)

print(result)

# 내 풀이
n, k = map(int, input().split())

cnt = 0
while n != 1:
    if n % k != 0:
        n -= 1
    else:
        n //= k
    cnt += 1

print(cnt)