プログラミング

最大二部マッチングとは 二部マッチング（bipartite matching）とは、グラフの中から辺の集合を選ぶ際に、選ばれたどの2つの辺も端点を共有しないようにする手法です。その中でも、最も多くの辺を選べるマッチングを最大マッチングと呼びます。 最大マッチングが求められた状態では、それ以上の辺を追加することはできません。仮に最大マッチング済みのグラフへ新たな辺を1本追加すると、その集合はもはやマッチングとして成立しなくなります。また、二部グラフでは最大マッチングが複数存在する場合もあります。 この問題は「応募者と求人の割り当て」といった形で、現実のマッチング問題によく例えられます。以下では

2次元平面上に n 個の点が与えられたとき、ユークリッド距離が最も小さい点の組み合わせ（最近接点対）を求める問題を扱います。愚直な全探索では O(n²) の計算量がかかりますが、分割統治法を用いることで O(n log n) で解くことが可能です。 問題の概要 点の集合 P = {p₁, p₂, ..., pₙ} が与えられたとき、以下を満たすペア (pᵢ, pⱼ) を見つけます。 min distance = √((xᵢ - xⱼ)² + (yᵢ - yⱼ)²) 入力と出力の例 入力: (2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4

ピーク要素とはある要素が、その上下左右の4つの隣接要素すべてと比べて「それら以上の値」を持つとき、その要素をピーク要素と呼びます。隣接要素とは、対象の要素の上・下・左・右に位置する要素のことであり、斜め方向の要素は隣接要素として考慮しません。また、行列の端にある要素については、境界の外側を無限大として扱うものとします。なお、1つの行列の中にピーク要素が複数存在することもあります。さらに重要な点として、ピーク要素は必ずしも行列内で最大の要素であるとは限りません。入力と出力入力:10  8  10  1014 13  

配列の転倒数（Inversion Count）とは、配列をソート済みの状態（昇順）へ変換するために必要な入れ替えの回数を表す指標です。添字のペア (i, j) について i < j かつ arr[i] > arr[j] が成り立つとき、そのペアは「転倒（反転）」していると定義されます。 配列がすでにソートされていれば転倒数は 0 になり、逆に配列が完全に逆順（降順）に並んでいる場合は転倒数が最大になります。 すべてのペアを総当たりで調べる素朴なアプローチでは O(n²) の計算量が必要ですが、マージソートを応用した分割統治法（Divide and Conquer）を用いることで、計

中央値（メジアン）とは中央値とは、データを昇順に並べたときにちょうど中央に位置する値のことです。累積的な割合でいえば、全体の50%の位置に相当する値であり、統計やデータ分析において最も基本的な指標の一つとされています。本記事では、「サイズが同じ2つのソート済み配列」から中央値を求めるアルゴリズムを紹介します。まずそれぞれの配列単体の中央値を求め、それらを比較しながら絞り込みを行うことで、2つの配列全体の実際の中央値を効率よく導き出します。入力と出力の例入力:ソート済みの2つの配列が与えられます。Array 1: {1, 2, 3, 6, 7}Array 2: {4, 6, 8, 10, 11}

二重連結グラフとは無向グラフにおいて、任意の2つの頂点の間に、途中の頂点を共有しない2本の経路が存在するとき、そのグラフは二重連結グラフ（biconnected graph／二頂点連結グラフ）と呼ばれます。言い換えれば、任意の2頂点が必ず何らかの閉路（サイクル）で結ばれている状態です。別の見方をすると、グラフGが連結であり、かつ関節点（articulation point、切断点）を1つも含まない場合、そのグラフは二重連結であると言えます。関節点とは、その頂点を取り除くとグラフが非連結に分割されてしまうような頂点のことです。この問題を解くには、深さ優先探索（DFS）を利用します。DFSでグラフ

幅優先探索（Breadth First Search：BFS）は、与えられたグラフのすべてのノードを訪問するための基本的なグラフ探索アルゴリズムです。この探索手法では、まず1つのノードを選択し、その隣接ノードを1つずつ順番に訪問していきます。ある頂点の隣接頂点をすべて処理し終えると、次の頂点へ移動し、同様にその隣接頂点を確認していくのが特徴です。BFSの仕組みとキューの役割BFSを実装するには、キュー（Queue）というデータ構造が必要です。探索対象となる隣接頂点はすべてキューに追加され、現在の頂点の隣接頂点の処理が完了すると、キューの先頭から要素を1つ取り出し、その頂点から再び探索を続けます

グラフにおける橋（ブリッジ）とは無向グラフにおいて、ある辺を取り除いたときにグラフが非連結になるとき、つまりグラフが複数の連結成分に分割されるとき、その辺は「橋（ブリッジ）」と呼ばれます。実用的な観点で考えると、ネットワーク内に橋が存在する場合、その接続が切断されるとネットワーク全体が分断されてしまう可能性があります。そのため、通信網や道路網などの信頼性・耐障害性を評価するうえで、橋の検出は非常に重要な問題となります。入力と出力入力: グラフの隣接行列 0 1 1 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 出力: 与えられたグラフの橋: Bri

木であるかの判定基準 この問題では、1つの無向グラフが与えられ、そのグラフが木（ツリー）であるかどうかを判定します。判定は木の性質を確認するだけで簡単に行えます。木には閉路（サイクル）が含まれないため、グラフ内に閉路がひとつでも存在すれば、そのグラフは木ではありません。 別のアプローチもあります。グラフが連結であり、かつ辺の本数が V−1 であれば、そのグラフは木であると判定できます。ここで V はグラフの頂点数です。これは「連結なグラフが V−1 本の辺を持つならば、必ず閉路を持たない」というグラフ理論の性質に基づいています。 入力と出力 入力： 隣接行列 0 0 0 0 1 0 0 0

グラフの連結性(接続性)を確認するには、何らかの探索アルゴリズムを用いてすべてのノードを巡回できるかどうかを試します。探索が完了した時点で、未訪問のノードが1つでも残っている場合、そのグラフは連結ではないと判断できます。有向グラフにおける連結性チェックのポイント無向グラフと異なり、有向グラフの場合はすべてのノードを起点として探索を行う必要があります。これは、あるノードに外向きの辺のみが存在し、内向きの辺がまったくないケースがあるためです。そのようなノードは、他のどのノードを起点にしても到達できません。本記事では、探索アルゴリズムとして再帰的なDFS(深さ優先探索)を採用します。入力と出力入力:

深さ優先探索（Depth-First Search：DFS）は、グラフを巡回するための基本的なアルゴリズムの一つです。開始頂点が1つ与えられると、隣接する頂点が見つかった時点でまずその頂点へ移動し、同じ要領でさらに奥へと探索を進めていきます。DFSは、行き止まりに達してそれ以上進めなくなるまで可能な限り深く探索を進め、その後バックトラック（後戻り）を行いながら、未訪問の頂点につながる新しい経路を探していきます。DFSを反復処理（イテレーティブ）な方法で実装する場合は、スタックというデータ構造を使用します。一方、再帰的に実装する場合は、関数呼び出し時に内部的にスタックが利用されるため、外部のスタ

この問題では、無向グラフと使用可能な m 種類の色が与えられます。課題は、グラフ上で隣接する2つの頂点が同じ色にならないように、m 色ですべてのノードへ色を割り当てられるかどうかを判定することです。解が存在する場合は、どの頂点にどの色が割り当てられたかを出力します。 頂点0から順に、各ノードへ1つずつ色を試していきます。ただし、色を割り当てる前に、その色が「安全」かどうかを必ず確認する必要があります。隣接する頂点のいずれかに同じ色が既に使われている場合、その色は安全ではないと判断されます。 この手法はバックトラッキングと呼ばれる探索アルゴリズムの一種です。ある色の選択によって後続の頂点で行き詰

Nクイーン問題（N-Queens Problem）は、チェス盤の上にN個のクイーンを、どのクイーンも他のクイーンを攻撃できないように配置する方法を求める、古典的な組合せ最適化問題です。チェスのクイーンは、縦・横・斜めのすべての方向に対して攻撃することができます。そのため、盤面上のどの2つのクイーンも同じ行・同じ列・同じ斜め線上に存在してはいけません。この記事では、クイーンの配置位置を表すために0と1からなるバイナリ行列を使用します。1が置かれたマスにクイーンが配置され、どのクイーンも他のクイーンを攻撃しない状態を表します。入力と出力入力： チェス盤のサイズ。通常は8（8×8が標準的なチェス盤の

この記事では、アルゴリズムの学習で定番となる「ラット迷路問題（Rat in a Maze）」について、問題の概要からバックトラッキングを使った解法、C++による実装例までをわかりやすく解説します。問題の概要N × N のサイズの迷路が与えられます。スタート地点は左上のセル、ゴール地点は右下のセルです。迷路には移動可能なセルと、通行止め（ブロックされた）セルが混在しています。ラットがスタート地点からゴール地点へ向かって移動するとき、「ゴールまでたどり着ける経路が存在するか」を判定し、存在する場合はその正しい経路をマークして出力するのがこの問題の目的です。迷路は二値マトリクス（0 と 1 のみで構

覆面算（クリプト算術）とは覆面算（Crypt-arithmetic problem）とは、アルファベットの各文字に異なる数字（0～9）を割り当て、算式が正しく成立するようにするパズルです。使用できる文字は最大10種類までで、それぞれの文字には0から9までのいずれかの数字が一意に対応します。典型的な問題では、2つの単語が与えられ、この2つの単語の和として表される3つ目の単語が答えになります。例えば「BASE」と「BALL」という2つの単語に対し、それぞれの文字に割り当てた数字で足し算を行うと、答えが「GAMES」になるような組み合わせを求めます。注意： 使用できる文字は必ず10種類以内である必要

部分集合和問題（Subset Sum Problem）は、整数要素を含む集合が与えられたとき、その中から要素の合計が指定された値と一致する部分集合をすべて見つけ出す古典的なアルゴリズム問題です。この問題の解法にはバックトラッキング（探索の巻き戻し）の手法が用いられます。候補となる要素を順番に部分集合へ追加していき、その要素が条件を満たさないと判断された時点で直前の状態に戻り、別の要素を試すことで効率的に解を探索します。入力と出力このアルゴリズムは、数値の集合と目標となる合計値を入力として受け取ります。以下は具体的な実行例です。入力: このアルゴリズムは数値の集合と合計値を受け取ります。 集合:

はじめに本記事では、数独（Sudoku／ナンプレ）として知られる有名な数字パズルを、コンピュータプログラムで解く方法を解説します。数独は 9×9 の数字グリッドで構成され、盤面全体はさらに 3×3 のブロック（ボックス）に分割されています。数独を解く際には、以下の基本的なルールに従う必要があります。使用する数字は 1〜9 のみです。同じ行、同じ列、そして同じ 3×3 ブロック内に、同じ数字を重複して配置することはできません。バックトラッキングによるアプローチここではバックトラッキング（後戻り法）アルゴリズムを用いて数独を解きます。バックトラッキングの流れは以下のとおりです。空きセルに数字を 1

ナイトツアー問題とはチェスにおいて、ナイト（騎士）は特殊な動き方をする駒として知られています。ナイトは「横に2マス・縦に1マス」あるいは「縦に2マス・横に1マス」という移動がどの方向にも可能で、その軌跡は英語の字母「L」字のような形になります。この問題では、空のチェス盤を用意し、盤上の任意のマスから出発したナイトが、盤上のすべてのマスを訪問できるかどうかを判定します。すべてのマスを訪問できる場合、各マスに出発点からそのマスに到達するまでの手数（ジャンプ回数）を記入していきます。この問題には複数の解が存在しえますが、ここでは1つの有効な解を見つけることを目標とします。このような組合せ最適化問題は

綱引きアルゴリズムとは 綱引きアルゴリズム（Tug of War）は、与えられた整数の集合を2つの部分集合に分割し、それぞれの合計値の差をできるだけ小さくするという問題を解くための手法です。イメージとしては、綱引きゲームに参加する2チームを、力がほぼ同等になるように振り分けることに相当します。 部分集合のサイズに関するルールは以下の通りです。 要素数 n が偶数の場合：各グループのサイズは n/2 ずつに分割します。 要素数 n が奇数の場合：一方のグループは (n−1)/2 個、もう一方は (n+1)/2 個に分割します。 入力と出力の例 入力: 異なる重みの集合 {23, 45, -3

この問題では、スペースなしで連結された1つの文と、有効な英単語からなる辞書が与えられます。私たちの課題は、この文を辞書に含まれる単語の組み合わせに分割できるすべての方法を見つけることです。解法の基本的な考え方は、文字列の左端から順に探索を行い、辞書に存在する有効な単語が見つかったら、その残りの部分に対して同じ処理を再帰的に適用するというものです。入力と出力入力: 有効な単語の集合（辞書）、および複数の単語がスペースなしで連結された文字列。 辞書: {mobile, sam, sung, man, mango, icecream, and, go, i, love, ice, cream} 対象