Python

この記事では、マージソート(Merge Sort)のアルゴリズムを使って配列を並べ替えるPythonプログラムについて、実際のコード例を交えながら詳しく解説します。 問題設定 課題 − 与えられた配列を、マージソートの考え方を用いて昇順に並べ替えます。 マージソートは分割統治法に基づく整列アルゴリズムです。まず配列を半分ずつ再帰的に分割し、要素が1つになった時点でそれを「ソート済み」とみなします。その後、隣り合う部分配列同士を先頭から比較しながら統合(マージ)していくことで、最終的に配列全体が整列されます。 Pythonでの実装例 # マージ関数 def merge(arr, l, m,

本記事では、以下の問題文に対する解決策について詳しく解説します。 問題文 コスト行列と目標位置 (m, n) が与えられたとき、開始地点 (0, 0) から (m, n) まで移動するための最小コストパスのコストを求めます。行列の各セルには、そのセルを通過する際にかかるコストが設定されており、移動は「右」「下」「右下」のいずれかの方向に進むことができます。 それでは、実際の実装を見ながら解決策を確認していきましょう。 実装例 # 動的計画法によるアプローチ R = 3 C = 3 def minCost(cost, m, n): # 初期化 tc = [[0 for x in

本記事では、次の問題に対するPythonでの解き方を詳しく解説します。 問題設定 問題文： 地点Aと地点Bの間に13の中間駅があるものとします。このとき、列車が2つの中間駅に停車する方法のうち、選んだ2駅が隣接しない（連続しない）ような組み合わせが何通りあるかを求めます。 解法のポイント n個の中間駅から、互いに隣接しないp個の駅を選ぶ方法の総数は、組合せの公式を使って次のように表せます。 C(n − p + 1, p) 今回の場合は n = 13、p = 2 なので、C(12, 2) = 66 通りという答えになります。 実装例 # 停車駅の組み合わせを求める関数 def stopping_

この記事では、以下の問題に対する解決策について詳しく解説します。 問題の概要 問題文： 与えられた配列を、ブリックソート（奇偶転置ソート）を用いて昇順に並べ替えます。 このアルゴリズムには「奇数フェーズ」と「偶数フェーズ」という2つの段階があります。奇数フェーズでは奇数番目のインデックスの要素に対してバブルソートを行い、偶数フェーズでは偶数番目のインデックスの要素に対してバブルソートを行います。これらを交互に繰り返すことで、配列全体が整列される仕組みです。 それでは、実際の実装例を見ていきましょう。 サンプルコード def oddEvenSort(arr, n): # ソート完了を判定

この記事では、クイックソート（QuickSort）のアルゴリズムを使って配列を並べ替えるPythonプログラムの実装方法を、初心者にもわかりやすく解説します。 問題の定義 問題： 与えられた配列を、クイックソートの考え方を利用して昇順にソートすることです。 クイックソートは「分割統治法」と呼ばれる手法に基づく高速なソートアルゴリズムです。まず配列を基準値（ピボット）を境目に2つの部分に分割し、それぞれの部分配列を再帰的にソートしていくことで、最終的に全体が整列された配列を得られます。 クイックソートの仕組み 処理の流れは以下のとおりです。 配列からピボット（基準となる要素）を選びます。こ

はじめに この記事では、再帰的な手法を用いた挿入ソートをPythonで実装する方法について解説します。 問題文 問題： 配列が与えられたとき、再帰的挿入ソートの考え方を使って昇順に並べ替えてください。 挿入ソートは、整列済みの部分配列を作りながら、そこへ要素を適切な位置に一つずつ挿入していくアルゴリズムです。通常はfor文などのループで実装されますが、今回は再帰呼び出しを利用して実装します。 アルゴリズムの流れ 先頭から n-1 個の要素を再帰的にソートする n 番目の要素（last）を取り出す last より大きい要素を後ろへ一つずつずらし、正しい位置に last を挿入する サ

Pythonの辞書（dict）は、最も頻繁に使用されるコレクション型データの一つです。キーと値のペア（key-value pair）で構成され、キーにはインデックスが割り当てられますが、値には必ずしも割り当てられません。Pythonには、さまざまなプログラムで辞書を簡単に扱えるようにする組み込み関数が数多く用意されています。この記事では、その中からupdate()、has_key()、fromkeys()という3つの組み込みメソッドについて詳しく解説します。update()メソッドupdate()メソッドは、2つ目の辞書の項目を1つ目の辞書にマージ（統合）することで、新しい項目を追加します。構

本記事では、以下の問題文に対する解決策について、Pythonでの実装方法をわかりやすく解説します。 問題の概要 問題文： 整数 n が与えられたとき、n 以下のすべての素数を出力してください。制約： n は小さな数とします。 素数を列挙する古典的な手法として知られる「エラトステネスの篩（Sieve of Eratosthenes）」は、指定した範囲内の素数を効率よく見つけるためのアルゴリズムです。それでは、実際の実装を見ていきましょう。 サンプルコード def SieveOfEratosthenes(n): # Trueで初期化されたboolean型の配列を作成 prime =

本記事では、ストゥージソート(Stooge Sort)を用いて配列を並べ替えるPythonプログラムの実装方法について解説します。 問題文 与えられた配列を、ストゥージソートというアルゴリズムを使って昇順に並べ替えることが課題です。 ストゥージソートとは ストゥージソートは、配列の一部を再帰的に繰り返しソートすることで全体を整列させる、非常にシンプルな比較ソートアルゴリズムです。計算量は O(nlog3/log1.5) ≒ O(n2.71) となり、バブルソートなどよりもさらに非効率ですが、再帰処理やアルゴリズム設計の仕組みを理解するための学習教材として知られています。 アルゴリズムの手順 1

Pythonの辞書（dict）は、最もよく使用されるコレクション型データ構造の一つです。辞書は「キー」と「値」のペアで表現され、キーにはインデックスが割り当てられますが、値には割り当てられません。Pythonには、さまざまなプログラムで辞書を簡単に操作できる組み込み関数が多数用意されています。本記事では、その中でも代表的な3つの組み込みメソッドであるcmp()、len()、items()について、具体例を交えながら詳しく解説します。 cmp()メソッドとは cmp()メソッドは、2つの辞書をキーと値に基づいて比較するためのメソッドです。重複する辞書の識別や、辞書間の大小関係の比較に役立ちます。

本記事では、以下の問題設定に対する解法を段階的に学んでいきます。 問題の定義 問題文： 負でない整数からなる配列（集合）と目標値 sum が与えられます。このとき、与えられた集合の部分集合のうち、その要素の合計が sum と一致するものが存在するかどうかを判定してください。 それでは、実際の実装を見ながら解法を確認していきましょう。 素朴なアプローチ（再帰） 最も直感的な方法は、各要素について「部分集合に含める」か「含めない」かの2択をすべて試す再帰的な探索です。最後の要素が sum より大きい場合は無視でき、それ以外の場合は「含める場合」と「含めない場合」のどちらか一方でも成功すれば Tru

Pythonには「Selenium」というパッケージがあり、これを利用することでWebドライバーを介したブラウザ操作を自動化できます。本記事では、PythonのSeleniumパッケージを使ってFacebookに自動ログインする方法を解説します。 全体の流れ Seleniumは、Webブラウザの操作を自動化・制御するための強力なパッケージです。このプログラムを実行するには、Python環境へのSeleniumのインストールに加えて、「geckodriver」と呼ばれるドライバーソフトウェアが必要になります。以下の手順で実現できます。 ステップ1：Seleniumのインストール まず、Pyt

画像解析を行う際には、Python向けのオープンソースライブラリ「OpenCV（Open Source Computer Vision Library）」が広く利用されています。OpenCVをインストールした後、プログラム内では「cv2」という名前でインポートして使用します。 本記事では、画像ファイルに含まれる輪郭（コンタ）を検出し、描画する方法を解説します。輪郭とは、画像内の物体の形状を把握するために重要な情報で、「同じ明るさ（輝度）を持つ領域の境界上にある点を結んだ線」として定義されます。OpenCVでは、輪郭の検出にfindContours関数、輪郭の描画にdrawContours関数を

この記事では、以下の問題文に対する解決策について学んでいきます。 問題文 ある整数 X が与えられます。X はマッチ棒で作るピラミッドの段数を表しています。X 段のマッチ棒ピラミッドを完成させるために必要な、マッチ棒の総本数を求めて表示してください。 考え方 マッチ棒で正三角形を組み上げていく場合、1辺に n 本のマッチ棒を使用するとき、必要なマッチ棒の総数は「3 × n × (n + 1) ÷ 2」で表されます。この公式を利用することで、x 段のピラミッド全体に必要なマッチ棒の総本数を簡単に計算することができます。 実装例 # 関数の定義 def numberOfSticks(x):

OpenCVはPython向けにcv2ライブラリを提供しており、コンピュータビジョンにおけるさまざまな形状解析に活用できます。本記事では、OpenCVを使って画像の中から「円」を検出する方法を解説します。円の検出にはcv2.HoughCircles()関数を使用します。この関数は、ハフ変換（Hough Transform）を用いてグレースケール画像から円を検出するものです。以下の例では、入力画像を読み込んだ後、そのコピーを作成し、ハフ変換を適用することで画像内の円を検出して出力します。構文cv2.HoughCircles(image, method, dp, minDist)各引数の意味は次の

はじめに この記事では、配列内の反転（インバージョン）をカウントする問題とその解決策について詳しく解説します。 問題定義 問題： リストが与えられたとき、その中に含まれる反転の数をカウントして表示します。 反転数とは、配列を昇順にソートされた状態にするために必要な入れ替え（スワップ）の回数を表す指標です。具体的には、i < j かつ arr[i] > arr[j] を満たす要素のペア（i, j）の総数として定義されます。 実装例 # 反転数をカウントする関数 def InvCount(arr, n): inv_count = 0 for i in range(n

テキスト分析では、さまざまなアルゴリズムで処理を行うために、単語を数えて重み付けすることがよくあります。本記事では、与えられた文中の各単語の頻度（出現回数）を求める方法を紹介します。主に以下の3つのアプローチがあります。1. collectionsモジュールのCounterを使う方法標準ライブラリのcollectionsモジュールに含まれるCounter()を使うと、単語の頻度を簡単に取得できます。まずsplit()で文章を単語に分割し、その結果に対してmost_common()を適用することで、出現回数の多い順に並べたリストが得られます。コード例from collections import

この記事では、「連続する1が存在しないバイナリ文字列の総数を求める」という問題の解き方について、Pythonでの実装例を交えながら詳しく解説します。 問題文 問題： 正の整数 N が与えられます。このとき、長さ N のバイナリ文字列（0と1のみで構成される文字列）のうち、連続する「1」が一切含まれないものの総数を求めてください。 例えば N = 3 の場合、有効な文字列は「000」「001」「010」「100」「101」の5つとなり、「011」「110」「111」は連続する1を含むため除外されます。 アプローチ：動的計画法 この問題は動的計画法（DP）を使うことで効率的に解けます。各桁の状態を

この記事では、与えられた整数の2進数表現に含まれる「1」の個数（セットビット数）をカウントするPythonプログラムについて解説します。問題定義整数 n が与えられたとき、その2進数表現の中に「1」がいくつ現れるかを求めます。この操作は一般にポピュレーションカウント（popcount）と呼ばれ、ビット演算やアルゴリズムの基礎を学ぶうえで重要なテーマです。例えば n = 15 の場合、2進数表現は 1111 となるため、セットビットの数は 4 になります。方法1：素朴なアプローチ（ループ処理）最も基本的な方法は、整数を右シフトしながら最下位ビットが1かどうかを順番に確認していくものです。サンプル

はじめに この記事では、与えられた整数の階乗（n!）に含まれる「末尾のゼロ」の個数を求めるPythonプログラムについて解説します。 問題文 整数 n が与えられたとき、n! の末尾に連続して現れるゼロの個数を数えます。例えば、10! = 3628800 であるため、末尾のゼロは2個です。 アプローチのポイント：なぜ「5」を数えるのか 階乗の末尾にゼロが付くのは、10 = 2 × 5 という因数の組み合わせが生まれるためです。n! の中では2の因数の方が5の因数よりも圧倒的に多く含まれるため、末尾のゼロの個数は「5の因数の総数」と一致します。 この性質を利用すると、次の式（レジャンドルの公