ブルートフォース

📌 アルゴリズムパターン

一般的なアルゴリズムアクセス方法を組み合わせて알고리즘 패러다임と呼ぶ.

📌 ブルートフォースの概要

Brute-Force Attack無差別対入攻撃だそうです.
例えば、パスワードが0000から9999までのロックがあると仮定します.
0000, 0001, 0002, ..., 9999まで可能なすべての数字を試してみることでパスワードを見つけることができます.브루트 포스は,ある問題に対して可能な限り多くの試行回数を行う最も純粋なアルゴリズム近接法である.

カードの団子が2つあります.左からカードを1枚、右からカードを1枚引いて、2つの数の積を最大にしたいです.近づく方法브루트 포스でアプローチしてみます.
ブルートフォスは可能な限りの数を確認した.

すべての可能な組み合わせにおいて、6 x 4=24を乗じると最大となる.

デッキ最大コンビネーション

문제カードが2束ある.
左の束からカードを1枚、右の束からカードを1枚引きたいのですが、2つの数の積が一番大きいです.どのようにして最大の積を求めることができますか?
関数max_productは、リストleft_cardsおよびリストright_cardsをパラメータとする.left_cardsは左の札団の数字を含み、right_cardsは右の札団の数字を含み、max_productはleft_cardsの中から1枚の札を抽出し、right_cardsの中から1枚の札を抽出したときの値が最大の値を返します.
💻 풀이

def max_product(left_cards, right_cards):
    result = []
    for i in left_cards:
        for j in right_cards:
            result.append(i * j)
    return(max(result))

print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

👉 출력

24
32
28

🧭 時間の複雑さ
len(left cards)はm,len(right cards)はnであった.
関数max productは左cardsサイクルの繰返し文に右cardsサイクルの繰返し文を重畳するため,max productの時間複雑度はO(mn)である.

📌 Brute Force評価

ブルートフォードアルゴリズムの入力が大きいほど効率が低下する.
📝 フルート砲の長所

は直感的に明確である.

の答えを正確に見つけることができます.

入力が大きくない場合は、Brute Forceを使用します.

一番近い売り場を探しています

売り上げが减ったので、支店を闭める危机に直面している.どのような支店を閉鎖すれば会社への打撃は小さくなりますか?お互いに近い売り場があれば、そのうちの1つが消えても大丈夫です.
社長が秘書に与えた任務は、直線距離が一番近い売り場を2つ探して報告することだ.
営業チームは各売り場の座標位置をスケジューラとして持ってきます.
tupleはx,y座標で各売り場の位置を表す.
0番売り場は(2,3)にあり、1番売り場は(12,30)にあります.
関数closetst_pairは、座標リストをパラメータとして受け入れ、リスト内の最も近い2つの売り場に[(x1, y1), (x2, y2)]形式で戻る.
2つの座標間距離を計算する関数distanceは、入力によって2つの図面を得、その間の直線距離を返す.
💻 풀이

from math import sqrt

def distance(store1, store2):
    return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

def closest_pair(coordinates):
    pair = [coordinates[0], coordinates[1]]
    for i in range(len(coordinates)):
        for j in range(i + 1, len(coordinates)):
            if distance(pair[0], pair[1]) > distance(coordinates[i], coordinates[j]):
                pair = [coordinates[i], coordinates[j]]
    return pair

test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))

🧭 時間の複雑さ
入力リスト座標の長さはnです.
関数closest pairには2つの重複文が重なり,2つの重複回数はいずれもnに比例する.したがって,関数の時間的複雑さはO(n^2)である.

江南駅豪雨

江南駅に大雨が降ったと仮定します.本当に災害映画の雨量で、高層ビルは雨で水没した.
そうなったとき、建物と建物の間にどれだけの雨が入るか知りたいです.それを計算する関数trapping_rainを書いてみました.
関数track rainは、建築高さ情報を格納するリストbuildingsをパラメータとして受信し、含まれる雨水の総量を返す.
たとえばパラメトリック建築[3,0,0,2,0,4]が入ってきました.では、0番索引には高さ33の建物、3番索引には高さ22の建物、5番索引には高さ44の建物があります.1番、2番、4番インデックスには建物がありません.
では、下の写真によると、全部で1010余りの雨を入れることができます.したがって、track rain関数は10を返します.
💻 풀이

def trapping_rain(buildings):
    rain = 0
    for i in range(1, len(buildings)-1):
        left = max(buildings[:i])
        right = max(buildings[i + 1:])
        min_floor = min(left, right)

        if min_floor - buildings[i] < 0:
            rain += 0
        else:
            rain += min_floor - buildings[i]
    return rain

print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

🧭 時間の複雑さ
室内建築の長さはnと言います.
まずfor文の繰返し回数はnに比例する.また、繰り返し文で最も時間がかかる部分はmax(buildings[:i])またはmax(buildings[i:])である.二つの中から一つ選びましょう
まず,buildings[:i]は最悪の場合O(n)である.そしてmax関数を用いて最値を探し,これもO(n)である.O(2 n)であるため、最終的にはO(n)となる.
for文の繰返し回数はnに比例し,for文の中で最も長い時間の部分はO(n)であるため,trapping_rain関数の時間複雑度はO(n^2)である.