Python

この記事では、以下の問題文に対する解決策について詳しく解説していきます。 問題文 問題： n個のアクティビティと、それぞれの開始時刻および終了時刻が与えられます。1人が同時に1つのアクティビティしか実行できないという条件のもと、実行できるアクティビティの最大数を選択してください。 変数の定義 N ― アクティビティの総数 S ― すべてのアクティビティの開始時刻を格納する配列 F ― すべてのアクティビティの終了時刻を格納する配列 アルゴリズムの考え方：貪欲法（グリーディ法） この問題は貪欲法を用いることで効率的に解くことができます。基本的な戦略は次のとおりです。 アクティビティを

はじめに 本記事では、「テキスト中からパターンとそのアナグラム（文字の並べ替え）をすべて検索する」という問題を、Pythonで解く方法を解説します。 問題の定義 問題文： テキストとパターンが与えられます。このとき、テキスト内に出現するパターン本体だけでなく、その並べ替え（アナグラム）すべての出現位置を出力してください。 たとえば、パターンが「TOR」であれば、「ROT」「OTR」「RTO」なども同じ文字構成を持つため、すべて検索対象となります。 アルゴリズムのポイント この問題はスライディングウィンドウ（滑動窓）の考え方を使うと効率的に解けます。手順は以下のとおりです。 パターンの各文

はじめに この記事では、以下の問題文に対する解決策について学びます。 問題文 − テキストとパターンが与えられたとき、テキスト内に含まれるパターンおよびその順列(アナグラム)の出現位置をすべて出力します。 例えば、テキストが「TUTORIALSPOINT」、パターンが「TOR」であれば、「ROT」や「OTR」といった並べ替えも検索対象となります。 アルゴリズムの考え方 この問題は、スライディングウィンドウ(滑動窓)と文字カウント配列を組み合わせることで効率的に解くことができます。手順は以下のとおりです。 パターン内の各文字の出現回数を、カウント配列 countP に記録します。 テキストの先

はじめにこの記事では、以下の問題に対する解決策について詳しく解説していきます。問題の概要問題文： 2つの数値が与えられたとき、その最大公約数（GCD）を計算して表示します。GCD（Greatest Common Divisor：最大公約数）とは、2つの数をどちらも余りなく割り切ることができる最大の整数のことです。ここではユークリッドの互除法を用いてGCDを計算します。この手法では、数値同士の割り算を繰り返し行い、余りが0になった時点で計算を終了します。ユークリッドの互除法の仕組みユークリッドの互除法は、次のような手順で動作します。2つの数 a と b を用意します。a が 0 の場合、b が最

はじめにこの記事では、「バイナリ挿入ソート（Binary Insertion Sort）」を使って配列を並べ替えるPythonプログラムについて解説します。名前の通り、このアルゴリズムは二分探索（バイナリサーチ）と挿入ソートの2つの考え方を組み合わせたものです。問題の概要問題文： 整数の配列が与えられます。バイナリ挿入ソートの手法を用いて、この配列を昇順に並べ替えてください。通常の挿入ソートでは、挿入すべき位置を先頭から順番に線形探索で探します。一方、バイナリ挿入ソートでは「すでにソート済みの部分列」に対して二分探索を適用することで、挿入位置を効率的に特定できます。実装例それでは、実際のコード

この記事では、BogoSort（ボゴソート）とも呼ばれる「順列ソート」をPythonで実装する方法について解説します。 問題の概要 問題文： 与えられた配列を、順列ソートの考え方を使って並べ替えます。 BogoSortは「生成と検証（generate and test）」というパラダイムに基づいたソートアルゴリズムです。仕組みは非常にシンプルで、以下の手順を繰り返します。 配列がソート済みかどうかを確認する ソート済みでなければ、配列をランダムにシャッフルする ソート済みになるまでこの処理を繰り返す 最悪の場合、計算量は O((n+1)!) となり、実用性はほとんどありませんが、アルゴリズ

この記事では、カクテルソート（Cocktail Sort）をPythonで実装する方法について解説します。サンプルコードと実行結果を通じて、アルゴリズムの仕組みをわかりやすく説明していきます。 カクテルソートとは カクテルソートは「双方向バブルソート」とも呼ばれるソートアルゴリズムです。通常のバブルソートが一方向のみの走査を行うのに対し、カクテルソートはリストを左右両方向に交互に走査しながら要素を並べ替えていく点が特徴です。 アルゴリズムの手順 1. 左から右への走査 まず配列を左から右へ走査します。走査中は隣接する要素同士を比較し、条件を満たしていれば値を入れ替えます。この処理により、配列内

はじめにこの記事では、コイン両替（Coin Change）問題をPythonで解く方法について詳しく解説します。動的計画法（Dynamic Programming）を活用することで、全探索よりもはるかに少ない計算量で答えを求めることができます。問題の定義額面の異なる複数のコイン（配列 S）と、その各額面が無限に供給される状況を考えます。このとき、目標金額 n を作り出す組み合わせが全部で何通りあるかを求めるのがこの問題です。なお、コインの並び順が違うだけのもの（例：「1枚＋2枚」と「2枚＋1枚」）は、同じ組み合わせとして1通りと数えます。単純な再帰で解くと同じ部分問題を何度も計算してしまい非効

この記事では、以下の問題文に対する解決策について詳しく解説します。 問題文 問題： 配列が与えられたとき、カウントソート（Counting Sort）のアルゴリズムを用いて、その配列を昇順に並べ替えます。 カウントソートとは？ カウントソートは、あらかじめ決められた範囲内のキーを対象として動作する整列アルゴリズムです。まず、それぞれ異なるキー（値）を持つ要素がいくつあるかを数え上げます。その後、累積和の計算を行うことで、各要素がソート後の配列のどの位置に配置されるべきかを求め、結果を出力します。 この手法は、キーの取り得る範囲が狭い場合に特に有効で、時間計算量は O(n + k)（n は要素数

はじめにこの記事では、以下の問題文に対する解決策について学びます。問題文長さ n のロッドと、n より小さい各サイズの切断片の価格を格納した価格配列が与えられます。ロッドを切断し、その断片を売却したときに得られる最大の価値を求める必要があります。この問題は、動的計画法（Dynamic Programming）を用いて解きます。アルゴリズムの考え方長さ i のロッドから得られる最大価値を val[i] とすると、次の漸化式が成り立ちます。val[i] = max(price[j] + val[i-j-1])　（j = 0 ～ i-1）これは「最初に j+1 の長さで切った場合の価格」と「残りの部

この記事では、次の問題に対する解決策をわかりやすく解説していきます。問題文配列が与えられたとき、サイクルソート（Cycle Sort）の考え方を用いてその配列をソートします。サイクルソートはインプレース（in-place）アルゴリズムの一種で、要素の入れ替え（スワップ）を「サイクル（循環）」を形成する形で行うのが大きな特徴です。理論上の書き込み回数が最小となるよう設計されているため、メモリへの書き込みコストが高い環境で特に有用とされるアルゴリズムです。それでは、以下の実装例で具体的な解決策を見ていきましょう。実装例def cycleSort(array): writes = 0

本記事では、「与えられた有向グラフの中にサイクル（閉路）が存在するかどうかを判定する」という問題を、Pythonを使って解決する方法を解説します。 問題の概要 問題文： 有向グラフが与えられたとき、そのグラフにサイクルが含まれているかどうかを判定してください。少なくとも1つのサイクルが存在する場合は True を、存在しない場合は False を出力します。 この問題は、グラフ理論における基本的かつ重要なトピックの一つです。例えば、タスクのスケジューリングや依存関係の管理において、循環参照（デッドロック）を検出する場面などで応用されます。 判定には深さ優先探索（DFS）を利用します。ポイントは

はじめに この記事では、次の問題文に対する解決策を、Pythonでの実装を通して学んでいきます。 問題文 40階建てのビルがあるとします。私たちが知りたいのは、「どの階から卵を落としても安全か」「どの階から落とすと卵が割れてしまうか」という情報です。ただし、使える卵の数には限りがあります。 そこで、全階層を確実に判定できる最悪ケースにおける最小の試行回数を求めて表示するプログラムを作成します。 これは「卵投下問題（Egg Dropping Puzzle）」として知られる、動的計画法の定番問題の一つです。 アルゴリズムの考え方 eggFloor[i][j] を「i個の卵を使ってj階までの建物を

この記事では、以下の問題文に対する解決策について詳しく解説していきます。問題文2つの整数が与えられたとき、それらの最大公約数（GCD）を計算し、結果を表示するプログラムを作成してください。拡張ユークリッドの互除法とはGCD（最大公約数）とは、2つの数をどちらも割り切ることができる最大の整数のことです。ここではユークリッドの互除法を用いてGCDを計算します。この手法は、2つの数を繰り返し割り算を行い、余りが0になった時点で計算を停止するというものです。さらに本記事では、通常のユークリッドの互除法を拡張したアルゴリズムを扱います。拡張ユークリッドの互除法では、再帰処理の過程で得られる以前の値を利用

この記事では、昇順にソートされた2つの配列から「目標値に最も近い合計を持つペア」を見つける問題と、その効率的な解法について詳しく解説します。問題文問題: ソート済みの2つの配列と目標値 x が与えられます。各配列から1つずつ要素を選んで作るペアのうち、その合計が x に最も近くなる組み合わせを見つけてください。解き方のポイント:二ポインタ法すべてのペアを総当たりで調べると計算量は O(m×n) になりますが、配列がソート済みであることを活かせば、二ポインタ法によって O(m+n) まで高速化できます。手順は以下の通りです。片方の配列は先頭から、もう片方の配列は末尾から走査を開始します。現在のペ

この記事では、ノームソート（Gnome Sort）と呼ばれるソートアルゴリズムについて学び、Pythonでの実装方法を解説します。問題定義与えられた配列（リスト）を、ノームソートのアルゴリズムを使って昇順に並べ替えることが目標です。ノームソートは、日常的な動作をモデル化した直感的なアルゴリズムです。庭の植木鉢を並べ替える「ノーム（小人）」の動きに例えられることから、この名前が付きました。バブルソートや挿入ソートに似た考え方に基づいています。アルゴリズムの手順1. 配列を左端から右端へ向かって走査する。 2. 現在の要素が前の要素以上であれば、そのまま1つ先へ進む。 3. 現在の要素が前の要素よ

この記事では、配列をヒープソート（Heap Sort）のアルゴリズムを使って並べ替えるPythonプログラムについて解説します。 問題の概要 問題文： 与えられた配列を、ヒープソートの考え方を用いて昇順にソートします。 ヒープソートでは、まず配列を最大ヒープ（親ノードが常に子ノード以上の値を持つ二分木構造）に構築します。その後、最大値であるルート要素を配列の末尾と交換し、残りの部分に対して再度ヒープ化を行うという操作を繰り返します。これにより、大きな値から順に後ろへ確定していき、最終的に配列全体がソートされます。 それでは、実際の実装例を見ていきましょう。 実装例 # ヒープ化処理 def h

この記事では、反復処理（イテレーション）のみでマージソートを実装する方法について解説します。再帰呼び出しを使わずに、whileループだけで配列を整列させる「ボトムアップ方式」のアプローチを見ていきましょう。 問題文 問題： 与えられた配列を、反復処理によるマージソートの考え方を用いて昇順に並べ替えてください。 例として、次の整数配列を扱います。 a = [2, 5, 3, 8, 6, 5, 4, 7] 反復マージソートの考え方 通常のマージソートは再帰を使って配列を分割しますが、反復版では最初から要素数1の部分配列として捉え、隣接する部分配列同士を統合（マージ）しながらサイズを倍々に増やしてい

この記事では、次の問題に対する解決策をPythonのコードとともに詳しく解説します。 問題の概要 問題文： 与えられた配列を、クイックソートの考え方を利用して反復的（非再帰的）な手法でソートします。 通常、クイックソートは再帰呼び出しによって実装されることが多いですが、ここでは明示的にスタックを使用することで、再帰なしに同じアルゴリズムを実現します。まず配列をパーティション（分割）し、その各部分を個別にソートしていくことで、最終的に全体がソートされた配列を得ます。 アルゴリズムの流れ ソート対象の範囲（開始インデックス l と終了インデックス h）をスタックにプッシュする。 スタックが空にな

本記事では、N枚のコインを三角形の形に配置したときに達成できる最大の高さを求めるPythonプログラムについて詳しく解説します。 問題文 N枚のコインが与えられ、それらを三角形の形に並べることを考えます。具体的には、1段目に1枚、2段目に2枚、3段目に3枚というようにコインを積み上げていきます。このとき、N枚のコインで作ることができる三角形の最大の高さ(段数)を求めて表示する必要があります。 解法のアプローチ 高さhの三角形を作るために必要なコインの総数は、等差数列の和の公式より次のように表されます。 1 + 2 + 3 + … + h = h(h+1)/2 ≤ N これを整理すると二次不