アルゴリズム4日目

(2021. 06. 17)

13日-映画監督

この問題は,問題を正しく理解することが重要であり,ブルートフォード概念を応用した問題である.ブルートフォースの概念は、すべての場合のすべての数を探し出し、条件に合致する事項を探し出す概念と理解できる.666を含む数字のうち、1つ目は666、2つ目は1666から7つ目は7666ではなく6660であることに注意して、本当に数字の大きさをすべて順番に並べて、666だけでいいのです.

に答える

While文に沿って、666文字列がある場合、n番目を検索し、数字を1つずつ増やして検索します.

N = int(input())
first = 666
while 1:
    if '666' in str(first):  # first 안에 666 들어있는지 확인
        N = N - 1  # 666이 있다면 N 을 하나씩 뺌
        if N == 0:  # 0 이되면 N 번째로 작은 종말 숫자라는 의미로 반복문 종료시킴
            break
    first = first + 1  # 근데 그 숫자에 666이 없으면 1을 더해가면서 first를 바꾸고 666 나올때까지 돌림 = 이렇게 모든 경우를 다따지는게 브루트 포스 개념
print(first)

点は「無限反復」と「検査済みn回」

14番-カタツムリvs棒

これはカタツムリが昼間に登ったり、夜に滑ったりして、最後に棒の頂上に着くのに必要な日数の問題です.n日かかる場合は、前に進む距離がA n、滑り出す距離がB(n-1)、前に進む距離が総ロッド長の日付を求めることができます.

import math
a, b, v = map(int, input().split())

day = math.ceil((v - b) / (a - b))

print(day)

の1回目の関数で解くと簡単ですが、上反りの理由は日中移動4のカタツムリ移動1の時にも棒に届くので上反りでいいです.1を移動しても、1を移動するためには、翌日の1日をかけて正常に戻るからです.

15-小数で元の数値を検索

薬水の個数と1と自分以外の薬水を与えるときは、薬水の持ち主の元の数字を見つけなければならない.

この問題は、薬水を一箱乗じて、平方根でいいということです.元の約数は前後に本来の数を乗じているので、約数が奇数であれば真ん中に1人の場合があるので平方にします.

また,この問題では,順序で与えられた約数ではないので,任意の2つの数字を乗じただけでは答えが見つからない.

n = int(input())
divisor_list = list(map(int, input().split()))

number = 1
for num in divisor_list:
    number *= num

real_num = (number ** 2) ** (1/n)

print(round(real_num))  # 제곱근 계산하면 정확히 정수로 나누어 떨어지지 않는 경우 있어서 반올림해야함. 예로 16찾을때 4096의 세제곱근은 15.999999 임....

を参照すると、四捨五入が必要になる場合があるので、最後にラウンド関数を使用し、平方根計算では整数に正確に分けることができないため、四捨五入が必要となる.

ex)16検索時、4096の立方根は15.99999999...

16-最大公約数、最小公倍数

2つの入力の約数を簡単に見つけることができ,最大公約数と最小公約数を求めることができ,ユークリッドアーク除算法を用いてアルゴリズムを記述することもできる.

ユークリッドアーク除算法は、2つの数字のうちの1つの小数(B)を2つの数の余剰(R 1)Bで割ったものをR 1で割ってR 2で割ったもので、余剰が0の場合の前余剰が最大公約数となる.

このようにして最大公約数を見つけた後、2つの数の積で最大公約数を除算すると、最小公倍数が得られる.

a, b = map(int, input().split())

def gcd(a, b):  # 최대공약수
    r = a % b
    while True:
        if r != 0:
            new_b = r  # b에 1번 나머지를 대입해야해서 나머지가 바뀌기전에 잠깐 저장해 둠
            r = b % r  # 새롭게 위에서 나온 나머지 = new b를 나눠줄 2번째 나머지를 구함
            b = new_b  # b에 1번 나머지를 대입해주고 과정을 반복시킴
        else:
            result = b
            break
    return result


def lcm(a, b):  # 최소공배수는 두수의 곱 나누기 최대공약수
    return int(a * b / gcd(a, b))

print(gcd(a, b), lcm(a, b), sep='\n')

17日-ホテルの部屋の手配

n n番目のお客さんが来たとき、質問で提示した条件で、一番近い部屋を手配したとき、部屋の番号の問題を出力します.

ルール1:お客様がn番目の場合、nを階数(H)で割って、残りが0であれば、お客様の部屋の階数はHで、湖水は数で割ってください.

ルール2:残りが0でない場合、層数は残り、湖は首の+1になります.

湖水が1の位置であれば桁数を調整する必要があるのでzfill()の方法で位置を調整します.

    if len(x) == 1:
        result = y + x.zfill(2)  # 두자리로 맞춰달라는 뜻
    else:
        result = y + x

x)x=2の場合x.zfill(2)=02

湖を作るために、各数字はstrに変換されて加算されます.

18-小数点を検索

これは小数を求める問題です.12番のように、12番の問題を参照してください.

19号-ハノイの塔

これはハノイのタワープロセスと最小移動回数を出力する問題であり,明確なブログリンクを残している.ハノイのtopアルゴリズム

この問題は再帰関数の概念を理解し運用するのに適した問題だと思います.n番目のどのような過程で結果を得るために,n番目のn−1番目のどのような過程がn番目とどのような関係があるかを探し出す再帰関数の設計1を学んだ.

これは不思議な経験で、起点、目的地、経由地を設計した後、ハノイの移行に必要なプロセスをアルゴリズムに整理し、設計した後、それをそのままコードに移行すれば問題を解決することができます.

に答える

n番目のタワーが1であれば、始点から目的地まで移動します.

1でなければn−1を起点として経由地を目的地として目的地を経由地として移転する.

n 1番目のタワーを起点から目的地に移動します.

n-1番目のタワーを経由地から出発点を経由して目的地に移動します.

がnが1になるまでこのプロセスを繰り返すと、タワーはすべて移動します.

def count(n):
    print(2 ** n - 1)  # 하노이의 탑 횟수 구하는 식

def move(start, to):  # N개의 탑을 시작점에서 목적지로 옮기는 함수
    print(f'{start} {to}')

def hanoi(N, start, to, via):  # 하노이 함수는 N개의 탑을 시작점에서 경유지를 거쳐 목적지로 가게하는 함수
    if N == 1:  # 옮겨야하는 것이 하나일 때가 오면
        move(start, to)  # 시작점에서 목적지로
    else:
        hanoi(N-1, start, via, to)  # 1이 아니면 그 앞 전 탑을 시작을 시작으로 경유지를 목적지로 삼고 목적지를 경유해서 다시 하노이 함수를 돌림
        move(start,to)  # 목적으로하는 n 번째 탑이 경유지로 모두 옮겨 지고나면 해당 탑을 시작에서 목적지로 옮김
        hanoi(N-1, via, to, start)  # 경유지에 남은 탑을 목적지로 옮기기 위해 시작점을 경유지로 두고 하노이 함수를 실행 시킴

n = int(input())
count(n)
hanoi(n, '1', '3', '2')

せきぶん

は、最初にプロセスを単純なプロセスとして設計し、アルゴリズム化した.

から、目的、経過した単語とコードの中の位置を混同しないで、表現します.

再帰関数を使用する場合と、単純に関数部分を記述する境界を決定します.
例えば

であり、上ではn番目の塔を除いてn−1部分が団塊に移行しなければならない過程である.つまり、n番目の塔では、すべての塔が経由地に移り、すべての塔が目的地に戻る場合が2種類ある.

20-座標を整列

x,yに関する座標は,xが基準ではなくyの昇順ソート法に関する問題である.

に答える

ランダという概念を学ぶのは初めてです.

ラムランは匿名関数の感覚ではなく、思考の流れに従って関数(特定の条件)を掛けて使用する関数です.

a.sort(key=lambda x: (x[1],x[0]))

sort関数はソート時にキー値を有し、指定しない場合は通常の基準で昇順、降順を行うことができる.

ここでキー値を指定すると、対応する条件に従ってソートされます.

その条件はramda関数であり,xをインデックス1優先順位付けの意味として書く.

せきぶん

二次元配列リストの展開と出力方法

for x, y in a:  # for를 한번만 써도 리스트 안에 있는 리스트의 요소를 풀어서 나타낼 수 있다.
    print(x, y)

21番-木を切る

高さhで樹木を切断し、上から伐採された樹木の和が所望の和以上である場合、最大高さhを求める問題.

に答える

二分探索を用いて高さを求める.

これらのナビゲーションには、ソートされたリストまたは範囲、開始点、終了点、中間値が必要です.

ea, m = map(int,input().split())
m_list = list(map(int,input().split()))

def m_search(m):
    start = 1  # 이건 1이든 0이든 상관없음 둘다 정답처리됨
    end = max(m_list)

    while start <= end:
        mid = (start + end) // 2
        m_sum = 0

        for tree in m_list:
            if tree > mid:
                m_sum += tree - mid
            else:
                m_sum += 0

        if m_sum >= m:  # 같아 졌을 때가 여기 붙어야 그때 start가 end를 넘어서면서 for문 탈출하고 값 반환 가능 
            start = mid + 1  # + 나무가 다 짝수인데 홀수 목표값이 있으면 정확히 안 나눠떨어지므로 같다는 조건이 아니라 end값 반환하는 방법으로 해야함
        else:
            end = mid - 1
    
    return end

print(m_search(m))

せきぶん

例題を代入し始めたばかりの頃、答えが出てきて、百俊を入れると、答えはずっと間違っていました.最初のコードには、ターゲットの長さとクリップされたツリーの長さの和が等しい場合、反例であるため、中間値が返されると書かれています.

所望の長さが奇数であり、与えられたツリーが偶数であれば、正しく分離されないため、誤った答えが出力される.

そのため、同じ時ではなく、木が伐採された高さがゴールに等しいので、ゴールに戻るように変更しました.

脱出whileの条件は、始点が終点より大きい瞬間であるため、長さの和が目標値以上の境界点では始点が終点より大きいため、重複文から脱出して高さを出力する.

中間検査

感想

今やっと40問の中で半分正解しましたが、最初は難しかったのですが、入力値を受け入れることに慣れた瞬間から、答えられると思います.もちろん、埋め込み関数の処理はよく知られておらず、どの関数をどのように使うか分からない人が多いので、どの問題もgooglingしなければならないが、アクセス問題や検索に必要な関数を検索する検索力が増えているようだ.概念を学ぶ感覚で探して、概念を勉強して、問題を解答します.

に決心させる

今は自分の力で一日中問題をつかむことが実力を高めることだとは思わないようだ.例えば、初めて数学の問題をするときは、概念をよく知っている例題をたくさん作ってこそ、次の応用問題が出たときに相応の概念を考え出して、頭から解答を出すことができるので、今は問題を解く考えで、概念を学ぶことを目的として、問題を解く方向を見つけました.もちろん、この過程で、問題に近づくことと解決することは自分の力にかかっている.長い目で見れば、焦らないで、勉強することが一番大切らしい.
人生は一度や二度で终わってしまうのではないでしょうか.