[これがコードテスト]23日目

▼▼緒論

今日は昨日学んだ動的計画法の例を説明します.

▼▼本題

📍 [問題1]1463-1

質問レッスンリンク(YouTube,39:00)
類似の問題
この問題は周知の動的プログラミング問題である.
フィボナッチ数列問題を図式化したように,問題を解く前に関数呼び出しの過程を直接描くことは理解に役立つ.
点火式は以下の通り.
a(i) = min(a(i-1), a(i-2), a(i-5)) + 1
点火後に1を加えるのは,関数の呼び出し回数を求める必要があるためである.
実際のコード実装では,1を減算した演算を除いて,この数を除算した場合にのみ点化式を適用する.
2つの数の中で単純により小さい数を求める場合、min()関数を使用します.
この問題をするとき、一つの事実の答えの例を見ても理解できない.だから私は他の人がどのように解いたのかを探しました.
これは、空のリスト(values)を発表し、それに追加する方法です.

# bottom_up 방식
n = int(input())

# 셋 중 편한식을 사용하자.
# 30001은 정수 X의 범위가 (1 <= x <= 30000)이기 때문에 1개를 더 추가해 작성했다.
array = [0 for _ in range(n+1)]
array = [0] * (n+1)
array = [0] * 30001

# 반복문의 범위가 2부터 시작하는 이유는 array [0], [1]이 모두 0이기 때문이다.
for i in range(2, n+1):
    if i == 1:
        continue

    values = []
    if i % 3 == 0:
        values.append(array[i//3] + 1)
    if i % 2 == 0:
        values.append(array[i//2] + 1)
    if i % 5 == 0:
        values.append(array[i//5] + 1)
    values.append(array[i - 1] + 1)

    array[i] = min(values)

print(array[n])
👉🏽 3

# bottom_up 교재 방식

n = int(input())

array = [0] * 30001

for i in range(2, n+1):
    d[i] = d[i-1] + 1
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)

print(d[n])
👉🏽 3

📍 [問題2]1726-2 x Nタイル

質問する
類似の問題
この問題は、ダイナミックプログラミングの基礎例に不可欠なフラット化問題のタイプでもあります.問題をよく見ると、最後に出力残りの10,007が表示されます.
これは結果値が大きくなる可能性があるからです.
式の最後に(d[x-1] + d[x-2]) % 10007を貼った.
タイルの問題を始めたばかりの頃は全然分からなかった.なぜ点火式を使うのか、どう書くのか分からず、絶望しました.
navin-ダイナミックプログラミングタイミング問題を解く編の講義を見て、点火式の書き方をよく説明したので、タイル問題はうまく解決できるはずです.
私のようにタイルの問題が理解できない人は밑져야본전の考えで授業をすればいいです.
白駿でタイル問題を何度かやっていて、点火式は基本的に大きな枠から外れていないような気がします.
点火式を求める場合は、まずN=1、N=2の時の数を求め、それから初めて発表された後、N-1、N-2の時の数を求めて終了します.
こうして自分で整理してみました.△私の足跡をご了承ください.

▼▼結論

授業を受けた時、羅東彬はコードテストでよく現れる問題のタイプの一つが現在学んでいる動的プログラミングだと言った.
解答にシャベルをたくさん使ったので時間が過ぎてしまいました😂 😂
明日までに、もう一度ダイナミック分割法の問題をして、感覚を熟知します.