[アルゴリズム]Intro
9つの独自の「プログラミング大会で学ぶアルゴリズム問題解決戦略」に基づいて作成された.
プログラミングコンテスト
タワーレコーダ、ACM-ICPC、コードパッケージ
アルゴリズムの問題ページ
プログラマー、バージュン、アルゴス駅、タックド
トラブルシューティングプロセス
問題を理解する
問題を読む過程と理解する過程
小さな制限条件でも、間違って理解しても解決できない問題はよくあります.
アルゴリズムの問題では,小さな誤りでも誤りとみなされることが最も重要なステップである.
再定義と抽象化
自分の言葉で自分の理解の問題を書く
直感的にわかりやすく
そして問題の抽象化を通じて、問題の本質だけを保留し、概括する.
問題の本質をどう見て、問題を容易にするか.
n/a.計画
問題の解き方を決める
使用するアルゴリズムと資料構造を選択します.
検証＃ケンショウ＃
実施前に計画を検証します.
設計したアルゴリズムがすべての場合に要求を満たすことを証明した.
実行時間やメモリなどが問題の制限を超えないようにする
修行する
計画に基づいて、コードで実現します.
振り返る
問題解決プロセスのレビューと改善
トラブルシューティングには影響しませんが、長期的なサポートを受けることができます.
有効な方法は、記録方法、悟り、間違いの原因などです.
トラブルシューティングポリシー
多くの問題に適用可能なアイデアからソート
類似タイプのチェック
形態や目標が似ているか、関連する問題を解決すれば、以前と似たような方法が期待できる.
しかし,このアルゴリズムの動作過程と原理を完全に理解してこそ,類似の問題に応用できる.
簡単な方法で始める
これは後で紹介する方法の一つであり,
무식하게 풀기のように時間と空間の制限を考慮せずに,問題を解決する最も簡単なアルゴリズムを創造する.この戦略の目標は簡単な難題の難解な誤りを予防することができる.
問題が一蹴でなくても,資料構造の最適化や計算繰返しなどによりアルゴリズムを改良して問題を解決することができる.
동적 계획법と関係があります.プロセス修飾
複数の簡単な入力を手で直接解決します.
直接問題を解決する過程を公式化することで,問題を解決する構想を導くことができる.
問題の簡略化
与えられた問題をもっと簡単にする.
制約を解消し,計算する変数数を減らし,多次元問題を一次元表現に簡略化するなど問題を簡略化する解法は,元の問題解法の直観性を提供するだけでなく,直接利用することもできる.
画像で表す
問題に関連する図を描き,解法の直感性を得る.
幾何学的図形は数列よりも直感的に受け入れやすい.
幾何学的な問題とは限らなくても、役に立ちます.
数式表示
評語で書く問題を公式で表す
数式の展開や縮小などの数学的操作は、問題の解決に役立ちます.
もんだいぶんかい
コンストレイントなどを分解して扱いやすくする方法
複雑な条件をより単純な形状の条件集合に分解することで操作を容易にする
ひそかに考える
問題の内在的な順序をどのように逆転するか
例えば、階段の中から欲しいものを選ぶなら、下から上がって確認するのが一番早い方法です.
強制順序
順序のない問題で順序を強制的に実行して問題を解く方法
答えに影響を与えない順序の制約を自動的に追加することで、問題解決方法を制限する数を減らすことができます.
よく犯す過ち
off by one
まちがっている
繰り返し文では、
>、<などの演算子と≥≤の演算子を混同したり、半開区間と閉鎖区間を混用したりします.防止の方法は,入力が最も少ない場合に,コードの動作方式を考慮してプログラムを記述することである.
スタックオーバーフロー
再帰呼び出しの深さが深すぎてプログラムが強制的に終了したエラー
C++ではスタックメモリを使用するとエラーが発生しやすいため、STLコンテナまたはグローバル変数を使用できます.
最大、最小エラー処理
予期した入力の異常を正しく処理できません.
可能な入力では、最小値または最大値を除外する必要がある問題が多いため、正しく動作するかどうかを考慮してエラーを見つけることができます.
例えば、自然数を入力と、小数であるか否かを判別する問題では、
1と2は一般少数の判別方式とはやや異なり、例外処理を行うべきである.
I/O速度が遅すぎる
テキストの入出力方法は様々ですが、方法によって速度の差が生じます.
入力または出力する変数が1万個を超える必要がある場合は、考慮すべきである.
あふれ出る
過大な値を処理すると、計算の中間または最後の計算結果にオーバーフローが発生し、値が変化します.
制限事項に区分された残りの部分を結果値として提示してもよい.
この場合、大規模な資料型を選択したり、他の制限事項の計算を中間プロセスに適用したりすることができます.
リソース・プロモーション
暗示的、暗示的な変換ともいえる.
多くの場合、気にする必要はありませんが、たまに難しい間違いを犯すこともあります.
時間の複雑さ
アルゴリズムの速度は反復文によって制御される.
定数の繰返し回数が大きいほどその影響は小さくなるからである.
したがって、通常は、繰り返し文を実行する回数を使用して実行時間を表す.
Big-O Notation
与えられた関数に成長が最も速い港湾を残し、残りの部分の記号を捨てます.
Oマーク法は関数の上限を大まかに表す.
ここで上限とは、Nが大きいほど最速成長項とその余項を含む項と大きく異なるため、上限と呼ぶ.
たとえば、次のBubbleソートがある場合:
def bubble_sort(arr):
for i in range(len(arr) - 1, 0, -1):
for j in range(i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]O(N²)に表示されます.
約1秒当たりの復唱回数が1億を超えると,時間制限を超える可能性がある.
Reference
この問題について([アルゴリズム]Intro), 我々は、より多くの情報をここで見つけました https://velog.io/@dlwpdlf147/알고리즘-Introテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol