[アルゴリズム]Greedy

グレースケールアルゴリズム
定義＃テイギ＃
今の状況では、グリディは今、良いものだけを選ぶ方法です.
ある種の符号化試験問題に遭遇し,すぐに問題タイプを特定することが困難である場合,그리디アルゴリズムを疑い,まず問題を解決できる貪欲な解決方法があるかどうかを考える必要がある.長い間考えても問題が解決しない場合は、後でDPや그래프 알고리즘などで問題を解決してみましょう.
実戦問題.
だいすうのほうそく
問題の説明
東彬の大数法則は,異なる数の配列がある場合,与えられた数をM回加算して最大数を形成する法則である.しかし,この法則の特徴は,配列された特定のインデックス(番号)の数がK回連続的に増加しないことである.
⚍▼I/O例
(入力)
5 8 3
2 4 5 4 6
(出力)
46
▼▼コードを書く

N, M, K = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort(reverse=True)
max1 = arr[0]
max2 = arr[1]
result = 0

result = (max1 * K + max2) * (M // (K + 1)) + max1 * (M % (K + 1))
print(result)

最初にこの問題に触れたときに、間違った問題を理解していたので、上記のI/O例については、6+6+5+5+4+4で追加すべきだと思いました^^;コードを書き終えて出力値と比較したとき、何か間違っていることに気づいて、もう一度説明して、最初の解釈とは異なるルールがあることを確定することができました.2行目に与えられた数字を降順に並べ替えると,最大数と2番目に大きい数だけを用いて解く問題が見つかり,与えられたK値に基づいて繰り返し増加する数のルールが見つかる.
回答例

# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
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) # 최종 답안 출력

ああ、幸いなことに、彼は本の中で与えられた方法に似ているようです.著者らの解釈のポイントも반복되는 수열에 대해서 파악である.著者らが提案した増加回数を事前に計算してから増加させる方法に加えて,全体的な解決法は類似しているようだ.
デジタルカードゲーム
問題の説明
デジタルトランプゲームは、複数のデジタルトランプの中で最も高いトランプを1枚選ぶゲームです.しかし、ゲームのルールを守ってトランプをするのは、次のようなルールです.
1 .数字が書かれたカードがNxMの形で並んでいます.Nは行数、Mは列数を表す.
2.ドローするカードを含む行を選択します.
3.選択した行の中で、一番低い数字のカードを選択します.
4.したがって、最初に選択する行を選択する際には、最後に最も数値の高い行を選択するために、後でその行の中で最も数値の低い行を選択することを考慮する必要があります.
⚍▼I/O例
(入力)
3 3
3 1 2
4 1 4
2 2 2
(出力)
2
(入力)
2 4
7 3 1 8
3 3 3 4
(出力)
3
▼▼コードを書く

N, M = map(int, input().split())
arr = []
result = 0
for i in range(N):
    line = list(map(int, input().split()))
    minimum = min(line)
    if result < minimum:
        result = minimum
print(result)

この問題は,N個の各行に対して最小値を抽出し,これらの値の中で最大値を探すことによって解決される.
回答例

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

いずれにしても、これは簡単な問題なので、同じように解決されていることが確認できます.
1まで
問題の説明
任意の数Nが1である前に、次の2つのプロセスのうちの1つを繰り返し選択して実行します.ただし,2番目の演算はNをKで割った場合にのみ選択できる.
1.Nから1を減算します.
2.NをKで割る.
NとKが与えられると、Nが1になるまで1回または2回のプロセスを実行する最小回数を求めるプログラムを作成します.
⚍▼I/O例
(入力)
25 5
(出力)
2
▼▼コードを書く

N, K = map(int, input().split())
count = 0
while N != 1:
    if N % K == 0:
        N //= K
    else:
        N -= 1
    count += 1
print(count)

問題の入力条件ではNとKの範囲が100000以下であるため,簡単な方法で解いた.一方,文の各繰返しでは,NがKで区切られている場合は,まずNを区切ることができ,そうでなければ1を相殺して最小繰返し回数を求めることができる.
回答例

# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)

本書の説明によれば、与えられたNに対して최대한 많이 나누기を実行すればよい.場合によっては、「2つ以上の数」が「1を減算」よりも多くの数字を減らすことができるからです.
📌 Nが100億以上の大数なら?
ソースコードは、NをKの倍数として効率的に減算するように記述される.
上記の答えの例は、この方法で作成されたコードです.
練習問題を作るときは、素早く問題を作ることも大切ですが、効率的に問題を作る必要があります.最も重要なのは,入力値の範囲が非常に大きい最悪の場合でも解くことである.これは重要なようです.
リファレンス
就職のためのコードテストで、Python|ナドンビン|韓光メディアを使って