データ構造とアルゴリズム (DSA) データを整理および保存する方法の研究と、これらのデータ構造上で動作する問題解決のための手順 (アルゴリズム) の設計を指します。 DSA は、すべてのコンピュータ サイエンスの学生が身につけなければならない最も重要なスキルの 1 つです。これらのテクノロジーについて十分な知識を持っている人は、他の人よりも優れたプログラマーであるため、ほぼすべてのテクノロジー大手の面接を突破できることがよく見られます。これ DSA チュートリアル データ構造とアルゴリズム (DSA) を迅速かつ簡単に学習できるようにすることを目的としています。
目次
- 検索アルゴリズム
- ソートアルゴリズム
- 分割統治アルゴリズム
- 貪欲なアルゴリズム
- 再帰
- バックトラッキングアルゴリズム
- 動的プログラミング
- グラフアルゴリズム:
- パターン検索
- 数学的アルゴリズム
- 幾何学的アルゴリズム
- ビットごとのアルゴリズム
- ランダム化されたアルゴリズム
- 分岐および拘束されたアルゴリズム
DSA の完全なフォーム
DSA という用語は、 データ構造とアルゴリズム 、コンピューターサイエンスの文脈で。
DSAとは何ですか?
データ構造とアルゴリズム (DSA) データを整理および保存する方法の研究と、これらのデータ構造上で動作する問題解決のための手順 (アルゴリズム) の設計を指します。
DSA を学ぶにはどうすればよいですか?
最も重要なことは、手順全体を、順番に実行する必要がある小さな部分に分割することです。 DSA をゼロから学習する完全なプロセスは、次の 5 つの部分に分かれています。
- 少なくとも 1 つのプログラミング言語を学習します (これはあなたの選択に任せます)。
- データ構造を学ぶ
- アルゴリズムを学ぶ
- 時間と空間の複雑さについて学ぶ
- DSA の練習問題
DSA を学ぶにはどうすればよいですか?
好みのプログラミング言語を学習できたことを願って、この DSA チュートリアルで DSA を学習する次のステップに進みましょう。
ここでは、データ構造とアルゴリズムを学習するためのロードマップの中で最も重要で最も待望される段階、つまり DSA について学習を開始する段階が始まります。 DSA のトピックは 2 つの部分で構成されます。
- データ構造
- アルゴリズム
これら 2 つは異なるものですが、相互に関連性が高く、最も効率的に学習するには正しい道に従うことが非常に重要です。どれを最初に学べばよいか迷っている場合は、このトピックに関する詳細な分析に目を通すことをお勧めします。 ここでは、データ構造を学習し、次にそのデータ構造で使用される最も関連性の高い重要なアルゴリズムを学習するフローに従いました。
データ構造を学ぶ
データ構造 データを効率的に整理してコンピュータのメモリに保存するのに役立つ重要なコンポーネントです。データを効果的に管理および操作する方法を提供し、より高速なアクセス、挿入、削除操作を可能にします。一般的なデータ構造には次のものがあります。 配列、リンク リスト、スタック、キュー、ツリー、グラフ それぞれが、当面の問題の要件に基づいて特定の目的を果たします。データ構造を理解することは、効率的なアルゴリズムを設計し、ソフトウェアのパフォーマンスを最適化するための基礎です。
配列 同じデータ型の要素のコレクションを格納する線形データ構造です。要素には連続したメモリが割り当てられ、定数時間のアクセスが可能になります。各要素には一意のインデックス番号があります。
- 配列に対する操作:
- トラバーサル : 配列の要素を反復処理します。
- 挿入 : 配列の特定のインデックスに要素を追加します。
- 削除 : 配列の特定のインデックスにある要素を削除します。
- 検索中 : 値またはインデックスによって配列内の要素を検索します。
- 配列の種類 :
- 1次元配列 : 単一次元の単純な配列。
- 多次元配列 : 行列などの複数の次元を持つ配列。
- 配列の応用 :
- データをシーケンシャルに保存する
- キュー、スタック、その他のデータ構造の実装
- 行列とテーブルの表現
- アレイに関する関連トピック:
- 配列のチュートリアル
- 面接における配列コーディングの問題トップ 50
- 配列に関する練習問題
2.文字列
あ 弦 は文字のシーケンスであり、通常はテキストを表すために使用されます。これは、コンピューター プログラムでのテキスト データの操作と処理を可能にするデータ型とみなされます。
- 文字列の操作 :
- 連結 : 2 本の文字列を結合します。
- 比較 : 2 つの文字列を辞書編集的に比較します。
- 部分文字列 抽出 : 文字列から部分文字列を抽出します。
- 検索 : 文字列内の部分文字列を検索します。
- 修正 : 文字列内の文字を変更または置換します。
- 文字列の応用 :
- テキスト処理
- パターンマッチング
- データ検証
- データベース管理
- 関連記事：
- 文字列のチュートリアル
- 面接における文字列コーディングの問題トップ 50
- 文字列の練習問題
3. リンクされたリスト
あ リンクされたリスト は、ポインタで接続されたノードにデータを格納する線形データ構造です。配列とは異なり、リンク リストは連続したメモリ位置に格納されません。
- リンクリストの特徴:
- 動的 : リンクされたリストは、ノードを追加または削除することで簡単にサイズを変更できます。
- 不連続 : ノードはランダムなメモリ位置に保存され、ポインタによって接続されます。
- シーケンシャルアクセス : ノードにはリストの先頭から順にのみアクセスできます。
- リンクされたリストの操作:
- 創造 : 新しいリンク リストを作成するか、既存のリストに新しいノードを追加します。
- トラバーサル : リストを反復処理し、各ノードにアクセスします。
- 挿入 : リスト内の特定の位置に新しいノードを追加します。
- 削除 : リストからノードを削除します。
- 検索 : リスト内で特定の値を持つノードを検索します。
- リンクリストの種類 :
- 単一リンクリスト : 各ノードはリスト内の次のノードを指します。
- 二重リンクリスト : 各ノードは、リスト内の次のノードと前のノードの両方を指します。
- 循環リンクリスト : 最後のノードは最初のノードを指し、循環ループを形成します。
- リンクリストの応用 :
- リンク リストは、次のようなさまざまなアプリケーションで使用されます。
- キューとスタックの実装
- グラフとツリーの表現
- 順序付けられたデータの保守
- メモリ管理
- 関連トピック：
- リンクリストのチュートリアル
- 面接用のリンク リストの問題トップ 50
- リンクされたリストに関する練習問題
4. マトリックス/グリッド
あ マトリックス 行と列に配置された要素の 2 次元配列です。これは、各要素が行と列の交差点にある長方形のグリッドとして表されます。
- 主要な概念:
- 行 : マトリックス内の要素の水平線。
- コラム : マトリックス内の要素の垂直線。
- 寸法 : 行列の行と列の数 (たとえば、3×4 行列には 3 行と 4 列があります)。
- 要素 アクセス : 要素には行インデックスと列インデックスを使用してアクセスできます (たとえば、M[2][3] は行 2、列 3 の要素を参照します)。
- マトリックス/グリッドの応用 :
- 画像処理
- データ分析
- 最適化の問題
- 関連記事：
- マトリックス/グリッドのチュートリアル
- 面接用マトリックス/グリッドの問題トップ 50
- マトリックス/グリッドに関する練習問題
5. スタック
スタック は、操作が実行される特定の順序に従う線形データ構造です。順序は次のとおりかもしれません LIFO(後入れ先出し) または FILO(先入れ後出し) 。 LIFO これは、最後に挿入された要素が最初に出力され、 行 これは、最初に挿入された要素が最後に出力されることを意味します。
- スタック上の操作 :
- 押す : スタックの先頭に要素を追加します。
- ポップ : スタックの先頭にある要素を削除して返します。
- ピーク : スタックの先頭にある要素を削除せずに返します。
- サイズ : スタック内の要素の数を返します。
- 空です : スタックが空かどうかを確認します
- スタックの応用例 :
- 関数呼び出し
- 式の評価
- 後戻り
- 操作を元に戻す/やり直す
- スタック上の関連トピック:
- スタックのチュートリアル
- 面接用に山積みされている問題のトップ 50
- スタック上の練習問題
6. 列
あ 列 データ構造は、特定の順序でデータを保存および管理するために使用されるコンピューター サイエンスの基本概念です。それは次の原則に従います 先入先出 ( FIFO )、キューに追加された最初の要素が最初に削除される要素です。
- キューの操作 :
- エンキュー : キューの最後尾に要素を追加します。
- それに応じて : キューの先頭から要素を削除します。
- ピーク : 前要素を削除せずに取得します。
- 空です : キューが空かどうかを確認します
- 一杯 : キューがいっぱいかどうかを確認します
- キューの種類 :
- 循環キュー : 最後の要素が最初の要素に接続します
- 両端キュー (Deque) ：両側から操作可能
- 優先キュー : 要素は優先度に基づいて配置されます
- キューの応用例 :
- ジョブのスケジュール設定
- メッセージキューイング
- シミュレーションモデリング
- データバッファリング
- 関連トピック：
- キューのチュートリアル
- 面接待ちの問題トップ 50
- キュー上の練習問題
7。 ヒープ
あ ヒープ は、ヒープ プロパティを満たす完全なバイナリ ツリー データ構造です。つまり、すべてのノードについて、その子の値がそのノード自身の値以下であるということです。通常、実装にはヒープが使用されます 優先キュー 、最小 (または最大) の要素は常にツリーのルートにあります。
- ヒープの操作 :
- 入れる : ヒープのプロパティを維持しながら、新しい要素をヒープに追加します。
- 最大抽出/最小抽出 : ルート要素を削除し、ヒープを再構築します。
- キーの増減 : ノードの値を更新し、ヒープを再構築します。
- ヒープの種類 :
- 最大ヒープ : ルート ノードはその子の中で最大値を持ちます。
- 最小ヒープ : ルート ノードはその子の中で最小値を持ちます。
- ヒープの応用 :
- 優先キュー
- 仕分け
- グラフアルゴリズム (ダイクストラアルゴリズムなど)
- 関連記事：
- ヒープのチュートリアル
- インタビュー用ヒープ上の問題トップ 50
- ヒープ上の練習問題
8. ハッシュ
ハッシュ化 と呼ばれる数式を用いて、可変サイズの入力から固定サイズの出力（ハッシュ値）を生成する技術です。 ハッシュ関数 。ハッシュは、データ構造内に項目を格納するためのインデックスまたは場所を決定するために使用され、効率的な取得と挿入を可能にします。
- 主要な概念:
- ハッシュ関数 : 入力をハッシュ値にマッピングする数学関数。
- ハッシュ表 : キーと値のペアを格納するデータ構造。キーはハッシュ値、値は実際のデータです。
- 衝突 : 2 つの異なるキーが同じハッシュ値を生成する場合。
- ハッシュ関数の種類 :
- 分割方法 : 入力を定数で除算し、その余りをハッシュ値として使用します。
- ミッドスクエア 方法: 入力を二乗し、中間の数字をハッシュ値として取得します。
- 折り方 : 入力を同じサイズのブロックに分割し、それらを加算してハッシュ値を取得します。
- 乗算方法 : 入力に定数を乗算し、小数部分をハッシュ値として取得します。
- 衝突解決テクニック :
- 個別のチェーン (オープン ハッシュ) : 衝突する要素を、対応するハッシュ値のリンク リストに格納します。
- オープン アドレッシング (クローズド ハッシュ) : さまざまな戦略を使用して、ハッシュ テーブル内で衝突要素の代替場所を見つけます。
- ハッシュの応用 :
- データベースとファイル システムにデータを効率的に保存および取得します。
- パスワードとデジタル署名の検証。
- リクエストを複数のサーバーに分散します。
- データの整合性と認証のために安全なハッシュを生成します。
- 関連記事：
- ハッシュのチュートリアル
- ハッシュに関する練習問題
9. 木
あ 木 は、エッジで接続されたノードで構成される非線形階層データ構造であり、ルートと呼ばれる最上位ノードと子ノードを持つノードを持ちます。コンピュータ サイエンスでデータを効率的に整理するために使用されます。
Javaのクラスとオブジェクト
- 木の横断 : ツリー トラバーサル手法は、ツリー データ構造内のノードにアクセスして処理するために使用されます。一般的な 3 つの走査方法は次のとおりです。
- 木の分類:
- の分類 木 特定の特性または基準に基づいてツリーをグループ化することを指します。これには、バランス係数、ノードの次数、プロパティの順序付けなどに基づいてツリーを分類することが含まれます。以下に、ツリーの重要な分類をいくつか示します。
| 分類 | 説明 | タイプ | 説明 |
|---|---|---|---|
| 学位別 | ツリーは、各ノードが持つことができる子の最大数に基づいて分類できます。 | 二分木 | 各ノードには最大 2 つの子があります。 |
| 三分木 | 各ノードには最大 3 つの子があります。 | ||
| N分木 | 各ノードには最大 N 個の子があります。 | ||
| 注文による | ツリーはノードとサブツリーの順序に基づいて分類できます。 | 二分探索木 (BST) | 左の子 |
| ヒープ | ヒープ特性を持つ特殊なバイナリ ツリー。 | ||
| 残高別 | 樹木は、バランスが取れているかどうかに基づいて分類できます。 | サブツリーの高さの違いは最大でも 1 です。例としては、AVL ツリーや Red-Black ツリーなどがあります。 | |
| アンバランスなツリー | サブツリーの高さは大幅に異なる場合があり、検索や挿入などの操作のパフォーマンスに影響します。 |
- 木の応用:
- ファイルシステム
- データベース
- XMLドキュメント
- 人工知能
- 関連記事：
- ツリーのチュートリアル
- ツリーコーディングの問題トップ 50
- ツリー上の練習問題
10. グラフ
あ グラフ は、有限の頂点 (またはノード) のセットと、ノードのペアを接続するエッジのセットで構成される非線形データ構造です。
- グラフの走査:
- 幅優先検索 (BFS) : ノードをレベルごとに訪問します。
- 深さ優先検索 (DFS) : ノードを再帰的に訪問し、一度に 1 つのブランチを探索します。
- グラフの応用 :
- ソーシャルネットワーク
- 地図とナビゲーション
- スケジュール設定
- データマイニング
- 関連記事：
アルゴリズムを学ぶ
という概念をクリアしたら、 データ構造 、さあ、旅を始める時が来ました。 アルゴリズム 。性質と使用法のタイプに基づいて、アルゴリズムは以下に示すようにいくつかのカテゴリにグループ化されます。
1. 検索アルゴリズム
検索アルゴリズム より大きなデータセット内の特定のデータを見つけるために使用されます。データ内のターゲット値の存在を見つけるのに役立ちます。検索アルゴリズムにはさまざまな種類があり、それぞれに独自のアプローチと効率があります。
- 最も一般的な検索アルゴリズム:
- 線形探索 : 一方の端からもう一方の端まで反復検索します。
- 二分探索 : ソートされた配列に対する分割統治型検索を行い、反復ごとに検索スペースを半分にします。
- 三項検索 : ソートされた配列に対する分割統治検索を行い、各反復で検索空間を 3 つの部分に分割します。
- その他の検索アルゴリズム:
- ジャンプ検索
- 補間検索
- 指数関数的検索
- 関連トピック：
- 検索アルゴリズムの練習問題
2. ソートアルゴリズム
並べ替えアルゴリズム リストの要素を数値順やアルファベット順などの特定の順序で配置するために使用されます。項目が体系的に整理され、特定の要素の検索やアクセスが容易になります。
並べ替えアルゴリズムにはさまざまな種類があります。広く使用されているアルゴリズムには次のようなものがあります。
おっとコンセプト
| ソートアルゴリズム | 説明 |
|---|---|
| バブルソート | 隣接する要素を繰り返し比較し、順序が間違っている場合は交換します。パスごとに、最大の要素がリストの最後に表示されます。 |
| 選択範囲の並べ替え | リストのソートされていない部分から最小の要素を見つけて、それを最初の要素と交換します。リスト全体が並べ替えられるまで、このプロセスを繰り返します。 |
| 挿入ソート | 未ソートの各要素をソート部分の正しい位置に挿入することにより、一度に 1 要素ずつソートされたリストを作成します。 |
| クイックソート | ピボット要素を選択し、ピボットに基づいてリストを 2 つのサブリストに分割し、同じプロセスをサブリストに再帰的に適用する分割統治アルゴリズム。 |
| マージソート | もう 1 つの分割統治アルゴリズムでは、リストをより小さなサブリストに再帰的に分割し、それらを並べ替えてから、それらを再び結合して並べ替えられたリストを取得します。 |
関連トピック：
- 並べ替えアルゴリズムのチュートリアル
- 面接の質問と問題のトップソート
- ソートアルゴリズムの練習問題
3. 分割統治アルゴリズム
分割統治 アルゴリズムは、問題を小さなサブ問題に分割し、それらのサブ問題を解決し、解決策を組み合わせて最終的な解決策を得るという再帰的戦略に従って問題を解決します。
手順:
- 分ける : 問題をより小さな独立したサブ問題に分割します。
- 征服する : 各部分問題を再帰的に解決します。
- 組み合わせる : 部分問題の解決策をマージして、最終的な解決策を取得します。
例:
- ソートのマージ: 配列を 2 つの半分に分割し、それぞれの半分を再帰的にソートし、ソートされた半分をマージします。
- クイック ソート: ピボット要素を選択し、ピボットに基づいて配列を 2 つのサブ配列に分割し、各サブ配列を再帰的にソートします。
- 二分探索: ターゲット要素が見つかるか、探索空間がなくなるまで、探索空間を繰り返し半分に分割します。
関連記事：
- 分割統治のチュートリアル
- 分割統治アルゴリズムに関する演習問題
4. 貪欲なアルゴリズム
名前が示すように、このアルゴリズムはソリューションを一度に 1 つずつ構築し、最も明白で即時の利益をもたらす次の部分、つまりその時点での最適な選択を選択します。したがって、局所的に最適なものを選択することが全体的な解決策にもつながる問題は、Greedy に最適です。
貪欲なアルゴリズムの重要な問題は次のとおりです。
| アルゴリズム | 説明 |
|---|---|
| フラクショナルナップザック | アイテムの端数を含めて、ナップザックに入れることができるアイテムの最大合計値を見つけます。 |
| ダイクストラのアルゴリズム | 加重グラフ内のソース頂点から他のすべての頂点までの最短パスを検索します。 |
| クラスカルのアルゴリズム | 重み付きグラフの最小スパニング ツリーを見つけます。 |
| ハフマンコーディング | 一連のシンボルに最適なプレフィックス コードを作成し、合計のエンコード長を最小限に抑えます。 |
関連記事：
- 貪欲なアルゴリズムのチュートリアル
- Greedy アルゴリズムの練習問題
5. 再帰
再帰 関数がそれ自身の定義内でそれ自体を呼び出すプログラミング手法です。通常、同じ問題をより小さなインスタンスに分割できる問題を解決するために使用されます。 例えば： ハノイの塔 (TOH) 、 階乗計算 そして フィボナッチ数列 等
ステップ :
- 規範事例 : 再帰呼び出しを停止し、解決策を提供する条件を定義します。
- 再帰的なケース : 問題を小さなインスタンスに分割し、再帰呼び出しを行う手順を定義します。
- 戻る : 再帰呼び出しから解を返し、それらを組み合わせて元の問題を解決します。
再帰が最もよく使用されるアルゴリズムの 1 つである理由は、それが他の多くのアルゴリズムの基礎を形成していることです。 ツリートラバース 、 グラフの走査 、 分割統治アルゴリズム そして バックトラッキングアルゴリズム 。
関連トピック：
6. バックトラッキングアルゴリズム
前述したように、 後戻り このアルゴリズムは再帰アルゴリズムから派生したもので、再帰的な解決策が失敗した場合に元に戻すオプションが付いています。つまり、解決策が失敗した場合、プログラムは失敗した時点まで遡って別の解決策を構築します。したがって、基本的には、考えられるすべての解決策を試して、正しい解決策を見つけます。
バックトラッキング アルゴリズムに関する重要かつ最も一般的な問題は、次に進む前に解決する必要があるものです。
| 問題 | 説明 |
|---|---|
| ナイトツアーの問題 | チェス盤上のナイトがすべてのマス目を正確に 1 回訪れるような一連の動きを見つけます。 |
| 迷路の中のネズミ | 障害物が壁として表されている迷路の開始位置から出口までの経路を見つけます。 |
| N-クイーン問題 | 2 人のクイーンが互いに攻撃しないように、N × N のチェス盤上に N 人のクイーンを配置します。 |
| 部分集合和問題 | 指定された合計を持つ指定されたセットのサブセットが存在するかどうかを判断します。 |
| 数独 | 1 から 9 までの数字を使用して 9×9 のグリッド パズルを解き、各行、列、および 3×3 のサブグリッドにすべての数字が反復せずに含まれるようにします。 |
関連記事：
- バックトラッキングのチュートリアル
- バックトラッキングアルゴリズムに関する練習問題
7。 動的プログラミング
動的プログラミング は、複雑な問題をより単純な部分問題に分割することで解決するために、数学とコンピューター サイエンスで使用される方法です。各部分問題を 1 回だけ解決して結果を保存することで、冗長な計算が回避され、幅広い問題に対するより効率的な解決策が得られます。
主要な概念:
- 最適な下部構造 : 問題に対する最適な解決策は、その部分問題に対する最適な解決策から構築できます。
- 重複する部分問題 : サブ問題は大きな問題の中で繰り返されることが多く、冗長な計算が発生します。
- メモ化 / 集計 : 再計算を避けるために部分問題の解を保存します。
動的計画アルゴリズムの重要かつ最も一般的な問題は、次に進む前に解決する必要があるものです。
| 問題 | 説明 |
|---|---|
| フィボナッチ数列 | 動的プログラミングを使用してフィボナッチ数を生成し、冗長な計算を回避します。 |
| 最長共通部分列 | 2 つのシーケンスに共通する最長のサブシーケンスを見つけます。 |
| 最長の増加サブシーケンス | 要素が昇順に並べ替えられた、指定されたシーケンスの最長のサブシーケンスを検索します。 |
| 0/1 ナップサック問題 | 指定された重量制限を超えない範囲で、指定された重量と値を持つアイテムを選択することによって取得できる最大値を決定します。 |
| ロッドの切断の問題 | 所定の長さのロッドを切断し、所定の価格に従って販売することで利益を最大化します。 |
| コイン両替問題 | 所定の硬貨の種類のセットを使用して、所定の金額を両替する方法の数を決定します。 |
| 距離の編集 | ある文字列を別の文字列に変換するために必要な操作 (挿入、削除、置換) の最小数を見つけます。 |
| 部分集合和問題 | 指定された合計を持つ指定されたセットのサブセットが存在するかどうかを判断します。 |
| 最長の回文部分列 | 回文である指定されたシーケンスの最長の部分シーケンスを見つけます。 |
| 最大サブアレイ合計 | 指定された 1 次元配列内で最大の合計を持つ連続した部分配列を見つけます。 |
| パーティションが等しいサブセットの合計 | 指定されたセットを合計が等しい 2 つのサブセットに分割できるかどうかを判断します。 |
| 最小コストパス | 指定されたグリッドの左上隅から右下隅までの最小コスト パスを見つけます。 |
| 最大積サブ配列 | 指定された 1 次元配列内で最大の積を持つ連続した部分配列を見つけます。 |
関連記事：
- 表化とメモ化
- 動的プログラミングの問題を解決するにはどうすればよいですか?
- 動的プログラミングのチュートリアル
- 面接用の動的プログラミングのコーディング問題トップ 50
- 動的計画法のアルゴリズムに関する演習問題
8. グラフアルゴリズム :
グラフアルゴリズム データ構造とアルゴリズム (DSA) では、ノードとエッジの集合であるグラフに関連する問題を解決するために使用される一連の技術と方法を指します。これらのアルゴリズムは、グラフに対して次のようなさまざまな操作を実行するように設計されています。 探索、横断、最短経路の発見 、そして決定 接続性 。これらは、ネットワーク ルーティング、ソーシャル ネットワーク分析、リソース割り当てなど、現実世界のさまざまな問題を解決するために不可欠です。
| トピック | トピックの説明 | アルゴリズム | アルゴリズムの説明 |
|---|---|---|---|
| グラフトラバーサル | グラフ内のすべての頂点にアクセスするためのテクニック。 | 深さ優先検索 (DFS) | 後戻りする前に、各分岐に沿ってできるだけ遠くまで探索します。 |
| 幅優先検索 (BFS) | 次のレベルの頂点に移動する前に、隣接する頂点を探索します。 | ||
| 最小スパニングツリー | 最小スパニング ツリーは、サイクルを形成せずにグラフ内のすべてのノードを接続する最小のツリーであり、可能な限り最短のエッジを追加することで実現されます。 | 接続された重み付きグラフの最小スパニング ツリーを見つけます。サイクルを形成しない最小の重みエッジを追加します。 | |
| また、接続された重み付きグラフの最小スパニング ツリーも見つけます。 2 つのツリーを接続する最小のウェイト エッジを追加します。 | |||
| トポロジカルソート | トポロジカル ソートは、頂点 u から頂点 v までのすべての有向エッジについて、順序付けにおいて u が v より前に来るようにする、有向非巡回グラフ (DAG) 内の頂点の線形順序付けです。 | カーンのアルゴリズム | カーンのアルゴリズムは、有向非巡回グラフ (DAG) のトポロジー的順序付けを見つけます。 |
| DFS ベースのアルゴリズム | DFS ベースのアルゴリズムは、深さ優先検索を使用して、有向非巡回グラフ (DAG) でトポロジカル ソートを実行します。 | ||
| 最短経路 | グラフ内の最短パスは、同じ 2 つの頂点間の他のすべてのパスと比較して、エッジに沿った重みの合計が最小となる、グラフ内の 2 つの頂点間のパスです。 | O(E * V logV) 時間ですべてのノード間の最短パスを見つける貪欲なアルゴリズム。 | |
| すべてのノードのペア間の最短パスを O(V^3) 時間で検索します。 | |||
| 単一ソースからの最短パスを O(V * E) 時間で検索します。 | |||
| ジョンソンアルゴリズム | すべての頂点ペア間の最短パスを O(V^2 logV + V * E) 時間で検索します。 | ||
| 強く接続されたコンポーネント | 有向グラフの強連結成分 (SCC) は、セット内のすべての頂点からセット内の他のすべての頂点へのパスが存在するような頂点の最大セットです。 | Kosaraju のアルゴリズムは、有向グラフの強連結成分 (SCC) を効率的に見つける 2 パス アルゴリズムです。 | |
| Tarjan のアルゴリズム | Tarjan のアルゴリズムは、有向グラフで SCC を見つけるためのもう 1 つの効率的なアルゴリズムです |
関連トピック：
- グラフのチュートリアル
- 面接におけるグラフコーディングの問題トップ 50
- グラフアルゴリズムの練習問題
9 。パターン検索
パターン検索 は、特定のテキスト内で特定のパターンの出現を見つけるために使用される DSA の基本的なテクニックです。
以下にいくつかの標準的なパターン検索アルゴリズムを示します。
| アルゴリズム | 説明 | 時間計算量 |
|---|---|---|
| 強引な | パターンとテキストのすべての部分文字列を比較します。 | O(分) |
| クヌース・モリス・プラット | 事前計算された失敗関数を使用して、不必要な比較をスキップします。 | O(m + n) |
| ボイヤー・ムーア | パターンを右から左に比較し、最後の不一致に基づいて文字をスキップします。 | O(分) |
| ラビン・カープ | ハッシュを使用して潜在的な一致を迅速にチェックします | O(m + n) |
関連トピック：
- パターン検索のチュートリアル
- 練習問題 パターン検索
10 。数学的アルゴリズム
数学的アルゴリズム は、数学的概念に関連する問題を解決するアルゴリズムのクラスです。これらは、コンピュータグラフィックス、数値解析、最適化、暗号化などのさまざまな分野で広く使用されています。
| アルゴリズム | 説明 |
|---|---|
| GCD そして LCM | 2 つの数値の最大公約数と最小公倍数を求めます。 |
| 素因数分解 | 数値を素因数に分解します。 |
| フィボナッチ数 | フィボナッチ数列を生成します。各数値は、前の 2 つの数値の合計になります。 |
| カタロニア語の数字 | 指定された数のかっこのペアを含む有効な式の数を数えます。 |
| モジュラー演算 | 指定された値を法とする数値の算術演算を実行します。 |
| オイラー係数関数 | 指定された数よりも小さく、それと相対的に素な正の整数の数を数えます。 |
| nCr の計算 | 二項係数を計算します。これは、n 個の要素のセットから r 個の要素を選択する方法の数を表します。 |
| 素数と素数性テスト | 指定された数値が素数かどうかを判断し、素数を効率的に見つけます。 |
| ふるいアルゴリズム | 指定された制限までのすべての素数を検索します。 |
関連トピック：
- 数学的アルゴリズムの練習問題
11. 幾何学的アルゴリズム
幾何学的アルゴリズム は、ジオメトリに関連する問題を解決するアルゴリズムのクラスです。幾何学的アルゴリズムは、次のようなコンピューター サイエンスの幅広い問題を解決するために不可欠です。
| アルゴリズム | 説明 |
|---|---|
| 凸包 | 一連の点を含む最小の凸多角形を検索します。 |
| 最も近い点のペア | セット内で互いに最も近い 2 つの点を検索します。 |
| 線の交差 | 2 本の線が交差するかどうかを判断し、交差する場合は交点を見つけます。 |
| ポリゴン内の点 | 指定された点が多角形の内側にあるか外側にあるかを判断します。 |
関連トピック：
- 幾何アルゴリズムの練習問題
12. ビットごとのアルゴリズム
ビットごとのアルゴリズム 数値の個々のビットを操作するアルゴリズムです。これらのアルゴリズムは、数値のバイナリ表現を操作して、ビット操作、ビットごとの論理演算 (AND、OR、XOR)、 ビットをシフトする 、 そして 設定 または 特定のビットをクリアする 数字の範囲内で。ビットごとのアルゴリズムは一般的に使用されます。 低レベルのプログラミング、暗号化、および最適化タスク 個々のビットの効率的な操作が必要な場合。
c 配列内の文字列
| トピック | 説明 |
|---|---|
| ビットシフト | 指定された位置数だけビットを左または右にシフトします。 |
| 左シフト (<<) | ビットを左にシフトし、実質的に数値を 2 倍します。 |
| 右シフト (>>) | ビットを右にシフトし、数値を実質的に 2 で割ります。 |
| 抽出ビット | マスクを使用して整数から特定のビットを抽出します。 |
| 設定ビット | マスクを使用して整数の特定のビットを 1 に設定します。 |
| ビットのクリア | マスクを使用して整数内の特定のビットを 0 に設定します。 |
| ビットの切り替え | XOR (^) を使用して、整数内の特定のビットを切り替えます。 |
| カウントセットビット | 整数内の設定されたビット (1) の数を数えます。 |
関連トピック：
- ビットごとのアルゴリズムのチュートリアル
- ビットごとのアルゴリズムの練習問題
13. ランダム化アルゴリズム
ランダム化アルゴリズムは、問題を解決するためにランダム性を使用するアルゴリズムです。彼らは目標を達成するためにランダムな入力を利用し、多くの場合、よりシンプルまたはより効率的なソリューションにつながります。
ランダム化アルゴリズムの種類:
- ラスベガス : 常に正しい結果が生成されますが、実行時間はランダムです。
- モンテカルロ : 低い確率で誤った結果が生成される可能性がありますが、実行時間は通常は速くなります。
ランダム化アルゴリズムを使用する重要なアルゴリズム:
| アルゴリズム | 説明 |
|---|---|
| クイックソート | 平均ケース時間計算量が O(n log n) のランダム化された並べ替えアルゴリズム。 |
| スキップリスト | 高速な検索および挿入操作を提供するランダム化されたデータ構造。 |
| ブルームフィルター | セットのメンバーシップを効率的にテストするための確率的データ構造。 |
14. 分岐結合アルゴリズム
の 分岐および拘束されたアルゴリズム は、最適な解決策を体系的に検索するために組み合わせ最適化問題で使用される手法です。これは、問題をより小さなサブ問題、つまり分岐に分割し、最適解の境界に基づいて特定の分岐を削除することで機能します。このプロセスは、最適な解決策が見つかるか、すべての分岐が探索されるまで続きます。
分岐限定アルゴリズムの標準問題:
| ユニークな問題 | 説明 |
|---|---|
| ブランチとバウンドを使用した 0/1 ナップザック | 0/1 ナップザック問題を解決するための分岐限定アプローチの実装の詳細。 |
| 最小コストの分岐とバインドを使用した 0/1 ナップザック | 最小コストの分岐限定手法を使用して 0/1 ナップザック問題を解決します。 |
| 8 パズル ブランチとバウンドを使用した問題 | 人気のスライディング パズル ゲームである 8 パズルの問題を解くための分岐と拘束のアプリケーションです。 |
| 分岐と結合を使用した N クイーン問題 | ブランチとバインドを利用して、古典的なチェス問題である N クイーンズ問題の解決策を見つけます。 |
関連トピック：
- 分岐結合アルゴリズムのチュートリアル
複雑さについて学ぶ
データ構造とアルゴリズム (DSA) の主な目標は、問題を効果的かつ効率的に解決することです。プログラムの効率を判断するために、次の 2 種類の複雑さを調べます。
- 時間計算量 : これにより、コードの実行にかかる時間がわかります。
- 空間の複雑さ : これにより、コードが使用するメモリの量がわかります。
漸近表記法 :
アルゴリズムの効率を比較するには、漸近記法、つまり次の値を推定する数学的ツールを使用します。 時間 に基づく 入力サイズ コードを実行せずに。プログラム内の基本的な操作の数に焦点を当てています。
| 表記 | 説明 |
|---|---|
| ビッグオー（Ο） | 最悪のシナリオを説明し、アルゴリズムの時間の上限を示します。 |
| オメガ (Ω) | アルゴリズムの下限時間制限を提供する、最良のシナリオを説明します。 |
| シータ (θ) | アルゴリズムのアルゴリズムの平均複雑さを表します。 |
コード分析で最も一般的に使用される表記法は次のとおりです。 ビッグオー表記 、入力サイズに関する実行時間またはメモリ使用量の上限を提供します。
関連トピック：
- 簡単な例で時間計算量を理解する
- さまざまなデータ構造の時間計算量
- アルゴリズムの複雑性分析のためにループを分析する方法
- 時間計算量解析に関する練習問題
練習問題のチートシート:
以下の記事から厳選された問題のリスト:
- DSA ロードマップ by Sandeep Jain
- SDE シート – SDE 準備のための完全なガイド
- techcodeview.com マスター シート – すべてのチートシートのリスト