グレーアルゴリズム近似法

このシリーズでは、タイプ別のアルゴリズムはアルゴリズムの深層概念ではなく、符号化テストに対して各タイプを簡単に参照します.
実際、授業を聞いた後、Pythonの初心者の立場に立って、基礎100題からジョージ高校のコアアルゴリズムに移ったほうがいいと思いますが、まず2強の半分に入ったことを整理しておきます.⭐️

グリディアルゴリズム

:現在の状況では、今すぐ選択する方法

正当性分析が重要です
->最良に見えるものを繰り返し選択するだけで、最良の解が見つかるかどうかをチェックする必要があります

問題1）おつりの問題

500元、100元、50元、10元のコインがあります.
おつりがN元の場合、おつりのコインの最低個数は?

に答える

ポリシー:最大のコインから計算
👀 最良の年を保証できる理由は?
大きい単位は小さい単位の倍数だから!
もう一度、グリディアルゴリズムは最小限のアイデアを考え出し、それが正当かどうかをチェックすることができるはずだ.
コード#コード#

n = 1260 #1260원이라고 가정
count = 0

array = [500, 100, 50, 10]

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

print(count)

時間複雑度分析:
通貨の種類がkである場合、時間的複雑度はO(k)に従う.
つまり、通貨の種類数の影響!

問題2)

どんな数Nが1になるまで
1.Nから1を引く
2.Nをkで割る(ただし、割る場合のみ)
1回または2回実行する最小回数は?

に答える

戦略:できるだけ多くの分配N~!
コード#コード#

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

while True:
  #N이 K로 나누어 떨어지는 수가 될 때까지 빼기
  target = (n // k) * k
  result += (n - target)

  #N이 K보다 작은 때 (더 이상 나눌 수 없을 때) 반복문 탈출
  if n < k:
    break
  
  #K로 나누기
  result += 1
  n //= k

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

問題3)

数字からなる文字列S.
数値の間に「x」または「+」を付けて最大の数値を作成します.

に答える

2つの数のいずれかで、1でない場合はプラス記号を実行します.そうでない場合は乗算記号

data = input()

#첫번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
  #두 수 중에서 하나라도 0 혹은 1인 경우, 더하기 수행
  num = int(data[i])
  if num <= 1 or result <= 1:
    result += num;
  else:
    result *= num;

print(result)