プログラミング

数式をコンピュータで計算する際には、前置記法（プレフィックス）や後置記法（ポストフィックス）の形式が用いられます。中置記法（インフィックス）から後置記法へ変換した後、正しい答えを得るためには「後置式の評価アルゴリズム」が必要になります。 後置式の評価においても、スタックというデータ構造を利用します。 後置式評価の基本手順 後置式を左から右へ読み進めながら、次のルールに従って処理を行います。 オペランド（数値）を見つけた場合：スタックにプッシュする 演算子を見つけた場合：スタックから2つの値をポップし、正しい順序で演算を実行する 演算結果は、その後の計算に備えて再びスタックにプッシュする 式全

問題の概要コインのリスト C(c1, c2, …, cn) と目標金額 V が与えられたとき、V をちょうど作るために必要なコインの枚数を最小化する問題を考えます。注意： 各種類のコインは無限枚使用できるものと仮定します。ここでは、コインの種類として C = {1, 2, 5, 10} が与えられている場合を扱います。各コインは何度でも使えるため、目標金額に対してできるだけ少ない枚数のコインを組み合わせて選ぶことになります。たとえば金額 22 の場合は {10, 10, 2} の 3 枚が最小となります。入力と出力入力：必要な金額。例：48出力：最小コイン枚数。この場合の出力は 7。48 =

この問題では、正の整数からなるリストが与えられます。各整数は、その位置から最大で何ステップ先へ進めるかを表しています。最初の要素から出発し、リストの末尾の要素に到達するまでに必要な最小ジャンプ回数を求めます。 動的計画法（DP）によるアプローチでは、最小ジャンプ回数を保存するための jumps 配列を定義します。たとえば jumps[i] には、配列のインデックス 0 からインデックス i に到達するまでに必要な最小ジャンプ回数が記録されます。 入力と出力 入力: 整数のリスト {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9} 出力: 末尾の位置に到達するための最小ジャンプ

すべての整数は、いくつかの平方数（完全平方数）の和として表すことができます。この問題では、与えられた値を表すために必要な平方数の項の最小個数を求めます。例えば、値が95の場合、95 = 92 + 32 + 22 + 12 と表せるため、答えは4となります。基本的な考え方は、1から順に平方数を調べていき、動的計画法（DP）によって各値ごとの最小項数を求めるというものです。値が1〜3の場合は1の二乗だけで構成するしかないため、そのまま1、2、3個の項が必要になります。入力と出力入力:整数値。例えば 63。出力:必要な平方数の項の個数。この場合の答えは 4。63 = 72 + 32 + 22 + 1

問題概要 数字キーパッドを持つモバイル端末が与えられます。現在押しているキーから移動できるのは上下左右のキーのみで、斜め方向のキーへの移動は許可されません。また、「*」と「#」のキーは押すことができません。 桁数 n が与えられたとき、これらのルールを守りながらキーパッド上で作成できる n 桁の数字列の総数を求めます。なお、同じキーを連続して押すこと（現在位置にとどまること）は許されるものとします。 入力と出力 入力: 桁数（例：3桁の数字） 出力: 与えられた条件を満たして作成できる3桁の数字列の総数。この場合の答えは 138 です。 アルゴリズム この問題は動的計画法（DP）を用いる

ある数値が与えられたとき、その数を n/2、n/3、n/4 に相当する3つの部分に分割し、得られる合計の最大値を求めるのがこの問題の目的です。 問題の概要 例として、50 は {25, 16, 12} に分割できます。次に、{25, 16, 12} の各値をさらに3つに分割し、これを繰り返します。すべての分割が完了した後、合計を計算してその最大値を求めます。 ただし、分割するとかえって合計が減ってしまう場合もあります。たとえば 5 を (5/2 + 5/3 + 5/4) = 2 + 1 + 1 = 4 と分割すると、元の値より小さくなります。そこで、「分割する」と「そのまま使う」のどちらか大き

ソート済みの整数集合と、各キーが検索される回数を示す頻度配列 freq が与えられたとします。ここでの課題は、これらのデータを用いて二分探索木（BST）を構築し、すべての検索にかかる合計コストを最小にすることです。部分問題の解を保存して再利用するために、補助配列 cost[n][n] を作成します。この cost 行列を利用することで、問題をボトムアップ方式で効率的に解くことができます。入力と出力入力: キー値（ノード）とその頻度。 Keys = {10, 12, 20} Frequency = {34, 8, 50} 出力: 最小コストは 142。 以下は、与えられた値から構成できるBSTの

ワイルドカードパターンマッチングとは この問題では、本文(メイン文字列)とワイルドカードパターンの2つが与えられます。アルゴリズムは、与えられたワイルドカードパターンが本文と一致するかどうかを判定します。 ワイルドカードパターンには、通常の英字のほかに「*」や「?」という特殊記号を含めることができます。「?」は任意の1文字に一致し、「*」は空文字列を含む任意の長さの文字列に一致します。 パターン照合の基本ルール パターンの文字が「*」の場合: 「*」自体を読み飛ばし、パターンの次の文字から照合を続けます。 パターンの文字が「?」の場合: 本文の現在の文字のみを読み飛ばし、パターンと本文の両方

問題の概要n人の友達からなるグループを考えます。各人はそのままシングルでいるか、他の友達とペアを組むことができます。このとき、全員がシングルまたはペアを組む方法の総数を求めるのが「友達ペアリング問題（Friends Pairing Problem）」です。なお、ペアを組む2人を p と q とすると、(p, q) と (q, p) は同じペアとして扱います。つまり、ペアの順序は区別しません。考え方（漸化式の導出）n人の友達について、シングルまたはペアを組む方法の数を f(n) とします。n番目の人に注目すると、状況は次の2つに分けられます。n番目の人がシングルのままの場合： 残りの (n-1)

回文分割とはこのアルゴリズムでは、文字列を入力として受け取ります。分割によって得られるすべての部分文字列が回文になっているとき、その分割を「回文分割（Palindrome Partitioning）」と呼びます。ここで扱う問題は、与えられた文字列を回文だけから構成されるように分割するとき、必要なカット（切り分け）の回数を最小化するというものです。たとえば「ababbbabbababa」という文字列は、「a | babbbab | b | ababa」のように3回のカットで、回文のみからなる部分文字列に分割できます。入力と出力入力: 文字列（例: ababbbabbababa） 出力: 回文と

パーティション問題とは、与えられた整数の集合を、それぞれの部分集合の要素の合計が等しくなるように2つに分割できるかどうかを判定する古典的なアルゴリズム問題です。 まず、与えられた集合の全要素の合計値を求めます。合計が偶数であれば、2つの集合へ分割できる可能性があります。一方、合計が奇数の場合は、合計の等しい2つの集合に分割することは不可能です。 合計が偶数である場合、「partTable」という名前の表（DPテーブル）を作成し、次の条件に基づいて問題を解いていきます。 partTable[i, j] は、array[0] から array[j-1] までの要素から選んだ部分集合の合計が i

最長回文部分列とは最長回文部分列（Longest Palindromic Subsequence）とは、与えられた文字列から一部の文字を選んで並べた「部分列」のうち、前から読んでも後ろから読んでも同じになる（回文となる）ものの中で、最も長いものを指します。この問題では、1つの文字列が与えられたとき、そこから作れる最長の回文部分列の長さを求めます。解法の考え方：漸化式この問題は動的計画法（DP）を使うことで効率よく解けます。基本となる漸化式は次のとおりです。L(0, n-1) を文字列全体に対する最長回文部分列の長さとすると、L(0, n-1) = L(1, n-2) + 2　※0番目と (n-

複数の行列が連鎖（チェーン）として与えられたとき、それらを掛け合わせるために必要なスカラー乗算の回数が最小になるような、最適な計算順序を求める問題を考えます。これが「行列連鎖乗積（Matrix Chain Multiplication）」と呼ばれる古典的なアルゴリズムの問題です。行列の乗算は結合法則が成り立つため、4つの行列 A・B・C・D がある場合、A(BCD)、(AB)(CD)、(ABC)D、A(BC)D のように、さまざまな順序で掛け合わせることができます。しかし、どの順序で計算しても最終結果は同じでも、途中で発生する演算の回数（計算コスト）は順序によって大きく異なります。そこで本記事

問題の概要整数のペアからなる列が与えられます。各ペアは2つの整数を持ち、必ず最初の整数の方が2番目の整数より小さいというルールがあります。チェーンの構築にも同じルールが適用され、ペア (p, q) の後にペア (x, y) を追加できるのは、q < x が成り立つ場合のみです。この問題を解くには、まず与えられたペアを最初の要素（a）の昇順にソートします。その後、各ペアの2番目の要素（b）と、それ以降のペアの1番目の要素（a）を比較しながら、動的計画法（DP）によって最長のチェーンの長さを求めます。入力と出力入力:数値ペアのチェーン {(5, 24), (15, 25), (27, 40)

0と1だけで構成された2値行列(バイナリ行列)が与えられたとき、その中から「すべての要素が1である正方形部分行列」のうち最も大きいものを見つけるのが、本記事で扱う問題です。 この問題は動的計画法(DP)を用いることで効率的に解くことができます。まず、元の行列と同じ大きさの補助的な「サイズ行列」を作成します。このサイズ行列の各要素 Size[i, j] には、「セル (i, j) を右下とする、すべて1で構成される正方形の一辺の長さ」を記録していきます。サイズ行列が完成した後、その中の最大値を調べることで、最大の正方形部分行列のサイズと位置を特定できます。 入力と出力 入力:2値行列 0 1 1

株式トレーディングにおいて、ある投資家が朝に株を買い、夕方に売るという取引を行います。1日に行える取引は最大2回までとし、2回目の取引は必ず1回目の取引が完了した後にのみ開始できるものとします。与えられた株価データをもとに、投資家が獲得できる最大の利益を求めるのがこの問題です。 入力と出力 入力： 株価リスト {2, 30, 15, 10, 8, 25, 80} 出力： 合計利益は 100 となります。 価格2で購入し価格30で売却 → 利益 28 その後、価格8で購入し価格80で売却 → 利益 72 よって合計利益は 28 + 72 = 100 アルゴリズムの考え方 この問題は動的計画法（

最大和増加部分列（Maximum Sum Increasing Subsequence）とは、与えられた整数列の中から選んだ部分列のうち、すべての要素が増加順に並んでおり、かつ総和が最大となるもののことです。 この問題は動的計画法（DP）を用いて解くのが一般的です。基本の考え方は、「配列の各位置 i に対して、arr[i] で終わる最大和増加部分列を記録しておく」というものです。i より手前にある各 j について「arr[j] < arr[i] であり、その時点で総和が最大となる部分列」を選び、その末尾に arr[i] を付け足すことで、L[i] を順次構築していきます。 入力と出力

整数値で構成される2次元行列が与えられたとき、要素の合計が最大になる長方形（場合によっては正方形）の部分行列を見つける必要があります。 このアルゴリズムの基本的な考え方は、まず左右の列を固定し、各行ごとに左端の列から右端の列までの要素の合計を計算して一時的な配列に保存することです。その後、この一時配列に対してKadane（カダネ）のアルゴリズムを適用して最大合計の部分配列、すなわち上端と下端の行番号を特定します。これにより、合計が最大となる長方形全体が確定します。 入力と出力 入力： 整数の行列。 1 2 -1 -4 -20 -8 -3 4 2 1 3 8 10 1 3 -

問題の概要 各セルに異なるコストが設定された行列が与えられ、あわせて目的地となるセルも指定されます。この問題では、開始セル (0, 0) から目的セルまで移動するときの「最小コスト経路」を求めます。 行列の各セルの値は、そのセルを通過する際にかかるコストを表しています。 移動できる方向には制限があり、あるセルからは「右」「下」「右下（斜め）」のいずれかにのみ進むことができます。 入力と出力 入力： コスト行列と目的地の座標。ここでは目的地を (2, 2) とします。 1 2 3 4 8 2 1 5 3 出力： (0, 0) から目的地まで到達するための最小コスト。この例では最小コストは 8

多角形において、互いに交差しない対角線によって三角形が形成されるとき、これを三角形分割（トライアンギュレーション）と呼びます。この記事では、数多くある三角形分割の中から、最小のコストとなる分割方法を求めるアルゴリズムを解説します。 三角形分割のコストは、その構成要素である各三角形の重みの総和として定義されます。各三角形の重みは、3辺の長さをすべて足し合わせた値、すなわち三角形の周長で求められます。 入力と出力 入力: 多角形の頂点の集合 {(0, 0), (1, 0), (2, 1), (1, 2), (0, 2)} 出力: 三角形分割の総コスト。この例では 15.3006 となります。 ア