プログラミング

ボイヤー・ムーア法にはいくつかのバリエーションがありますが、ここで紹介するのは「グッドサフィックス（良い接尾辞）ヒューリスティック」と呼ばれるアプローチです。この手法では、検索に先立って事前処理としてサフィックステーブル（接尾辞表）を作成します。 最大の特徴は、パターンの末尾の文字から照合を開始する点です。テキスト側の部分文字列がパターンの一部と一致した場合、その一致した部分が再び現れる可能性のある位置へとパターンをずらし（シフトし）ながら探索を続けます。さらに、パターンの接頭辞（プレフィックス）がテキストの接尾辞（サフィックス）と一致する箇所を探して移動することもあります。どちらにも該当し

クイックソートは、リストを2つの部分に分割することで並べ替えを行う高速なソートアルゴリズムです。まず、パーティション（分割）処理によって基準となる「ピボット」要素を選択します。ピボットより小さい値は左側に、大きい値は右側に配置されます。この分割処理が完了した後、それぞれの部分リストに対して同じ手順を再帰的に適用していくことで、全体を整列させます。 クイックソートの計算量 時間計算量： 最良ケース・平均ケースで O(n log n)、最悪ケースで O(n²) 空間計算量： O(log n)（再帰呼び出しによるスタック領域） 平均的には非常に高速に動作するため、実務でも広く利用されている代表的

基数ソートとは基数ソート（Radix Sort）は、非比較型のソートアルゴリズムの一つです。クイックソートやマージソートのように要素同士を比較して大小関係を判定するのではなく、整数キーを構成する各桁に着目し、同じ位（けた）・同じ値を持つ数字同士をグループ化することで整列を行います。「基数（radix）」とは記数法における底（base）のことです。私たちが日常的に使う10進法では基数が10であるため、10進数のデータをソートする際には、0〜9までの10個のポケット（バケット）を用意して数値を振り分けることになります。基数ソートの計算量時間計算量：O(nk)（nは要素数、kは最大桁数）空間計算量：

選択ソート（Selection Sort）は、リストを「整列済みの部分」と「未整列の部分」の2つに分けて処理するシンプルなソートアルゴリズムです。まず配列の中から最大値または最小値を探し出します。ここでは最小値を取り上げると、見つけた最小値を先頭の要素と入れ替えることで、リストの先頭に配置します。この操作を1回行うごとに、整列済みの部分が1つずつ増え、未整列の部分は徐々に小さくなっていきます。これを繰り返すことで、最終的に配列全体が昇順（または降順）に並び替えられます。選択ソートの計算量時間計算量：O(n2)空間計算量：O(1)データ数nに対して比較を繰り返すため、時間計算量はO(n2)となり

シェルソート（Shell Sort）は、挿入ソートを改良したソートアルゴリズムです。通常の挿入ソートでは、要素を正しい位置に挿入する際に、隣接要素との比較・移動を繰り返すため、大きなブロックを何度もシフトしなければならないケースがあります。シェルソートでは、あらかじめ一定の間隔（ギャップ）を設定して離れた位置にある要素同士を比較・交換することで、大規模なデータ移動を効率的に削減できます。各パスが終了するごとにギャップを半分に縮小していき、最終的にギャップが1になった時点でほぼ整列された状態になるため、挿入ソートよりも高速に動作します。シェルソートの計算量時間計算量： 最良の場合は O(n lo

活動選択問題（Activity Selection Problem）は、開始時刻と終了時刻を持つ n 個の異なる活動が与えられ、その中から一人の人間が時間の重複なく実行できる活動の最大数を選択する古典的なアルゴリズム問題です。この問題は貪欲法（グリーディ法）を用いて解くのが一般的です。基本的な考え方は、「残りの活動の中で最も早く終わる活動」を順に着目し、その開始時刻が「直前に選択した活動の終了時刻」以降であれば採用する、というものです。終了時刻の早い活動から優先的に選ぶことで、後続の活動に使える時間を最大化できます。計算量活動リストがソートされていない場合：O(n log n)ソート済みのリス

隣接リスト形式で表現されたグラフ G(V, E) と始点（ソース）頂点が与えられているとき、ダイクストラ法を用いることで、始点からグラフ内の他のすべての頂点への最短経路を求めることができます。この問題を解くには、次の2つのリストを使用します。確定済みリスト： 最短経路木としてすでに確定した頂点を格納します。未確定リスト： まだ確定していない頂点を保持します。アルゴリズムの各ステップでは、未確定の頂点の中から始点からの距離が最小となる頂点を選び出し、確定済みリストへ移動させます。また、各頂点の先行ノード（直前のノード）を記録するリストも用意します。この先行ノードを逆にたどることで、始点から目的地

この問題は前回のものと基本的に同じで、始点ノードから他のすべてのノードへの最小距離を求めることが目的です。最大の違いは、グラフを隣接行列(この用途ではコスト行列もほぼ同じ役割を果たします)で表現している点です。 隣接行列を用いた場合の時間計算量は O(V²) です。ここで V はグラフ G(V, E) のノード数を表します。 入力と出力 入力:隣接行列 出力: 0 から 1 へ、経由: 0、コスト: 3 0 から 2 へ、経由: 1、コスト: 5 0 から 3 へ、経由: 1、コスト: 4 0 から 4 へ、経由: 3、コスト: 6 0 から 5 へ、経由: 2、コスト: 7 0 から 6

ハフマン符号化（Huffman Coding）は、データを一切失うことなく元の状態に復元できる「可逆圧縮」を実現する、代表的なデータ圧縮アルゴリズムです。このアルゴリズムでは、入力された各文字に対して可変長の符号を割り当てます。符号の長さは文字の使用頻度と密接に関連しており、出現頻度の高い文字ほど短い符号を、出現頻度の低い文字ほど長い符号を受け取ります。これにより、データ全体のサイズを効率的に削減できます。 ハフマン符号化の基本的な流れ ハフマン符号化の処理は、主に以下の2つの段階で構成されます。 ハフマン木（Huffman Tree）の構築：各文字の出現頻度をもとに、優先度付きキューを

はじめに 以前のハフマン符号化の問題では、頻度のリストはソートされていませんでした。しかし、頻度のリストがあらかじめソートされた順序で与えられている場合は、符号の割り当て処理をより効率的に行うことができます。 この手法では、2つの空のキューを使用します。まず、一意な文字ごとに葉ノードを作成し、頻度の昇順でキューに挿入していきます。 このアプローチにより、アルゴリズムの計算量はO(n)に抑えられます。 なぜ2つのキューでO(n)が実現できるのか 通常のハフマン符号化では優先度付きキュー(ヒープ)を利用するため、計算量はO(n log n)となります。一方、頻度がソート済みであれば、次のような仕

問題の概要 この問題では、複数のジョブ（仕事）からなるリストが与えられます。各ジョブには「締め切り（デッドライン）」と「利益」が設定されており、すべてのジョブは1単位時間で完了するため、締め切りの最小値は1です。ある時刻に実行できるジョブは1つだけという制約のもとで、合計利益を最大化するジョブの実行順序を求めるのが目的です。 この問題は貪欲法（グリーディ法）によって効率的に解けます。まず、すべてのジョブを利益の降順にソートします。次に、利益の高いジョブから順に、「そのジョブの締め切り以前にある空きスロットのうち最も遅いもの」へ割り当てていきます。価値の高いジョブを優先的に配置しつつ、締め切り

バケットソート（バケット整列法）は、データ要素をあらかじめ用意した複数の「バケット（bucket）」に振り分けていくソート手法です。各バケットには値の範囲が似たデータが格納されるため、分散後に各バケットを個別に別のソートアルゴリズムで整列させ、最後にすべての要素を元のリストへ順番に集約することで、ソート済みの配列が得られます。バケットソートの計算量時間計算量：最良ケース・平均ケースで O(n + k)、最悪ケースで O(n2)空間計算量：最悪ケースで O(nk)入力と出力の例入力: 未ソートのデータ列: 0.25 0.36 0.58 0.41 0.29 0.22 0.45 0.79 0.01

コムソートは、バブルソートの改良版として知られるソートアルゴリズムです。基本的な考え方はバブルソートと共通していますが、両者には重要な違いがあります。バブルソートでは、毎回のパスにおいて隣接する要素同士を比較して並べ替えます。一方、コムソートでは、あらかじめ決めた一定のギャップ（間隔）を空けた要素同士を比較します。そして、各パスが完了するたびにギャップを縮小していき、最終的にギャップが1になった時点でバブルソートと同じ動作になります。ギャップを縮小する際の係数（シュリンクファクター）は 1.3 が推奨されています。つまり、各パスが終わるごとにギャップの値を1.3で割っていくことになります。この

カウントソート（計数ソート）とはカウントソートは安定なソート手法の一つで、比較的小さな整数値をキーとして要素を並べ替えるために用いられます。同じキー値を持つ要素の個数を数え、その情報をもとに各要素の正しい位置を決定するのが大きな特徴です。この手法は、キーとなる数値同士の差（最大値と最小値の範囲）がそれほど大きくない場合に非常に効果的です。逆に、値の範囲が広すぎるとカウント用の配列が巨大になり、空間計算量が増大してしまう点には注意が必要です。カウントソートの計算量時間計算量：O(n+r)（n は要素数、r はキーの範囲）空間計算量：O(n+r)入力と出力入力:ソートされていないデータのリスト:

サイクルソートとは サイクルソート（Cycle Sort）は、インプレース型（追加メモリをほとんど使わない方式）のソートアルゴリズムの一つです。要素同士を比較しながら並べ替える比較ベースのソートであり、他のインプレース型ソート手法に対しても効率的に動作します。 最大の特徴は、ソートを完了するために必要なメモリへの書き込み回数が理論上最小であるという点です。このため、EEPROMやフラッシュメモリのように書き込み回数に制約がある記憶媒体を扱うシステムで特に有用とされています。 サイクルソートの計算量 時間計算量：O(n²) 空間計算量：O(1) 入力と出力 入力： ソートされていないデー

ヒープソートとは ヒープソート（Heap Sort）は、「ヒープ」というデータ構造を利用して行うソートアルゴリズムの一つです。ヒープは完全二分木であり、大きく分けて次の2種類があります。 最小ヒープ（Min-Heap）： 根（ルート）の要素が常に最小値となる構造 最大ヒープ（Max-Heap）： 根の要素が常に最大値となる構造 ヒープソートでは、まずデータ列から最大ヒープを構築します。次に、根にある要素（最大値）を取り出し、配列の末尾の要素を根へ移動させます。この入れ替えによってヒープの性質が崩れるため、配列全体を再びヒープ化（再ヒープ化）します。この「根から削除 → 再ヒープ化」の操作を

挿入ソートは、トランプの手札を並べ替えるときの操作によく似た整列アルゴリズムです。カードゲームで手札を昇順に整理する場面を思い浮かべてください。新しいカードを引いたら、すでに並んでいるカードの中から適切な位置を見つけて、そこに差し込みますよね。まさにこれが挿入ソートの基本的な考え方です。具体的には、データ集合から1つの要素を取り出し（この値を「キー」と呼びます）、そのキーを挿入できる隙間を作るために、左側にあるより大きい要素を順番に右へずらしていきます。そして、正しい位置が見つかったところでキーを挿入します。これを配列の末尾まで繰り返すことで、全体が昇順に整列されていきます。挿入ソートの計算量

マージソート（Merge Sort）は、分割統治法（Divide and Conquer）に基づいた代表的なソートアルゴリズムです。データセット全体を小さな部分に分割し、それぞれをソートしながら大きな塊へと統合していくことで、最終的に整列済みの配列を作り上げます。マージソートの大きな特徴は、最悪ケースでも計算量が O(n log n) と安定している点です。クイックソートのように最悪時に O(n²) へ劣化することがないため、性能の予測がしやすく、大規模なデータや外部ソートにも広く利用されています。マージソートの計算量時間計算量： 最良・平均・最悪のすべてのケースで O(n log n)空間計

鳩の巣ソートとは鳩の巣ソート（Pigeonhole Sort）は、非比較型ソートに分類される整列アルゴリズムの一つです。比較演算によって大小関係を判定するクイックソートやマージソートとは異なり、値そのものを「穴（ホール）」に振り分けることで並べ替えを行います。この手法は、ソート対象の要素数と、キーとなり得る値の範囲がほぼ同じである場合に特に高い効果を発揮します。具体的な手順は以下のとおりです。まず、値の範囲に応じた個数の「穴」を用意します。次に、各要素をその値に対応する穴へ挿入し、最後に穴から先頭の要素を順番に取り出して配列へ格納すれば、整列された結果が得られます。鳩の巣ソートの計算量時間計算

Gitの「スタッシュ(stash)」機能を使うと、リポジトリ内のコード変更を一時的に保存し、後で取り出すことができます。 Gitリポジトリで作業していると、ファイルに加えた変更を、後ほどコミットに含めたいケースがよくあります。そんなときに役立つのが git stash コマンドです。スタッシュを利用すれば、作業中ブランチ上のコード変更を一時退避させ、別の作業に集中できます。本記事では、実例を交えながらGitにおけるスタッシュの基本と git stash コマンドの使い方を解説します。 Gitスタッシュとは? スタッシュとは、作業ディレクトリとインデックスにある変更を一時的に保存するための機能で