ブログ｜プログラミングの練習

【プログラミング基礎】アルゴリズム表現の共通言語「疑似コード（Pseudocode）」の読み方・書き方ガイド

アルゴリズムの解説書や基本情報技術者試験などでよく使われる「疑似コード（Pseudocode）」の書き方・読み方の基本ガイドです。

特定のプログラミング言語に依存せず、処理のロジックを直感的に表現するための共通文法を分かりやすくまとめました。

1. 入出力と関数の宣言

アルゴリズムの前提条件（入力）と、最終的に得られる結果（出力）を明記するための記述です。

Input / Output / return

Input: 〇〇     // 入力や関数の引数などを記述

Output: 〇〇    // 出力や関数の返り値を記述

return 値       // 関数の返り値として、値を返す

2. 制御構造（繰り返し・条件分岐）

処理の流れ（ループや分岐）を構造化して表現します。

① for文（指定回数の繰り返し）

for 変数 = 値1 to 値2 do

処理

end for
変数の値を「値1」から「値2」まで、1ずつ増やしながら処理を実行します。
② while文（条件を満たす間の繰り返し）

while 条件 do

処理

end while
条件が「真（True）」の間、処理を実行し続けます。
③ if文（条件分岐）

if 条件 then

処理1

else

処理2

end if
条件が真ならば「処理1」を、偽（False）ならば「処理2」を実行します。

3. 演算子とデータ構造

代入、比較、論理演算、および配列の参照方法です。

代入・比較・論理演算・配列

# 代入演算

変数 = 値              // 変数に値を代入

# 比較演算

値1 == 値2            // 値1と値2が等しければ真、異なれば偽

値1 != 値2            // 値1と値2が等しくなければ真、等しければ偽

# 論理演算

条件1 and 条件2       // 条件1と条件2がともに真のとき真（AND）

条件1 or 条件2        // 条件1または条件2のいずれかが真のとき真（OR）

# 配列構造

配列名[添字]           // 配列の指定された添字（インデックス）番目の要素を参照

4. 補足：疑似コードを実際のプログラムに落とし込む例

【疑似コードを使ったアルゴリズム例（配列の合計値を求める）】

文法例を組み合わせて作成したサンプル疑似コードです。

Input: 配列 A, 要素数 N

Output: 合計値 total

total = 0

for i = 0 to N - 1 do

    total = total + A[i]

end for

return total

■ 疑似コードを使うメリット

Python、Java、C言語など、言語ごとに異なる文法差異を気にせず、「アルゴリズムの本質的なロジック（解法手順）」だけに集中して設計・共有できるのが最大の強みです。

5. まとめ

・基本構文：for / while による繰り返しと if ... else による条件分岐を明示する。

・終了タグ：end for や end if でスコープの終わりを明確にする。

・演算と参照：== や != で比較し、配列名[添字] で要素を取り出す。

アルゴリズムを学ぶ際やアイデアをコードに落とし込む前の整理に、ぜひ疑似コードを活用してみましょう！

【プログラミング基礎】アルゴリズムの考え方｜「総当たり」と「近似アルゴリズム（ヒューリスティクス）」の違いを徹底解説

プログラムで問題を解決する際、状況や規模に応じて適切な「アルゴリズムのアプローチ（考え方）」を選ぶことが非常に重要です。

今回は、すべてのパターンを検証する「総当たりアルゴリズム」と、現実的な時間で実用的な解を見つける「近似アルゴリズム（精度保証・ヒューリスティクス）」について、具体例を交えて解説します。

1. 総当たりアルゴリズム（Brute Force Algorithm）

考えられるすべての条件や組み合わせを順番に試し、確実に正解を導き出す最もシンプルで確実な手法です。

特徴とメリット・デメリット

・解の確実性：すべての可能性を検証するため、解が存在すれば必ず正解（最適解）を見つけられます。

・計算量の問題：データ数や組み合わせが増えると計算時間が爆発的（指数関数的）に増加します。

【総当たりの具体例：4桁のダイヤルロック解除】

0000、0001、0002 …… 9999 まで、最大 10,000 通りを順番にすべて試せば必ず開きます。

しかし、これが桁数の多いパスワードや都市を巡るルート選択になると、計算に何年・何百年もかかるようになります。

2. 近似アルゴリズム（Approximation Algorithm）

すべての組み合わせを試すと途方もない時間がかかる問題に対し、「100%の最適解ではなく、十分に満足できる“正解に近い解”を素早く探す」手法です。

近似アルゴリズムは、精度の保証があるかどうかで大きく2つに分類されます。

① 精度保証付きアルゴリズム

・得られる解が「理論上の本当の正解からどのくらいの誤差（例：真の最適解の1.5倍以内など）におさまっているか」が数学的に証明・保証されている手法です。

・品質の一定ラインを絶対に確保したい重要な計算システムなどで利用されます。
② 発見的手法（ヒューリスティック / Heuristics）

・数学的な精度保証はないものの、「経験則」や「直感的なルール」に基づいて現実的な時間内でそこそこ良い解を導き出す手法です。

・遺伝的アルゴリズムや貪欲法（Greedy Algorithm）などが代表例です。AIやゲームの思考ルーチン、配送ルートの最適化などで広く活用されています。

3. 補足解説：NP困難問題と現実的なアプローチ

【なぜ「妥協のアルゴリズム」が必要なのか？】

■ 組み合わせ爆発（巡回セールスマン問題の例）

「複数の都市を最も短い距離で一度ずつ巡って戻ってくるルート」を探す問題（巡回セールスマン問題）では、都市が30個になるだけでルートの組み合わせは $10^{32}$ を超え、最新のスーパーコンピュータで総当たりしても宇宙の年齢以上の時間がかかります。

■ 現代プログラミングでの使い分け

このように厳密な正解を求めることが現実的に不可能な問題（NP困難問題など）に対して、「数分〜数秒で95点の解を出す」ために近似アルゴリズムやヒューリスティクスが活躍します。

プログラミングでは、常に100点満点の厳密解を目指すのではなく、問題の規模や制限時間（レスポンス速度）に応じてアルゴリズムを使い分ける思考が重要です。

4. まとめ

・総当たりアルゴリズム：全パターン検証。確実に正解が出るが、要素が増えると時間がかかりすぎる。

・精度保証付きアルゴリズム：正解に近い解を求め、誤差の範囲が理論的に証明されている。

・ヒューリスティック（発見的手法）：精度保証はないが、経験則を用いて高速に実用的な「良い解」を見つける。

アルゴリズムの基礎知識として、「厳密さ（確実性）」と「計算スピード（実用性）」のトレードオフの関係を理解しておきましょう！

【Javaで学ぶアルゴリズム】ユークリッドの互除法で最大公約数（GCD）を求める｜自作ロジックとBigInteger活用

取り上げるテーマは、紀元前から伝わる世界最古のアルゴリズムの一つ「ユークリッドの互除法」です。

アルゴリズムの基本概念からJavaでの自作実装、さらには実務で役立つJava標準ライブラリ（BigInteger）を使った一発解決法まで詳しく解説します。

1. ユークリッドの互除法とは？

2つの整数の最大公約数（GCD: Greatest Common Divisor）を効率よく見つけるための定番手法です。

アルゴリズムの定理

2つの整数 $X, Y$ ($X \ge Y$) について、

「$X$ を $Y$ で割った余りを $R$ とすると、$X$ と $Y$ の最大公約数は、$Y$ と $R$ の最大公約数に等しい」

この性質を利用し、余り $R$ が 0 になるまで計算を繰り返すことで、どんなに大きな数字同士でもすばやく最大公約数を導き出すことができます。

2. Javaでの実装例（自作ロジック）

まずは、アルゴリズムの仕組みを理解するために while 文を使って自作してみましょう。

サンプルコード（GCDSample.java）

public class GCDSample {

    public static void main(String[] args) {

        int x = 1071;

        int y = 1029;



        int result = getGcd(x, y);

        System.out.println(x + " と " + y + " の最大公約数は " + result + " です。");

    }

    // 最大公約数を求めるメソッド

    public static int getGcd(int x, int y) {

        // R = 0 となるまで、YとRを変えながらループ

        while (y != 0) {

            int r = x % y; // 剰余Rを求める

            x = y;         // 次の計算のためにYをXに代入

            y = r;         // 次の計算のためにRをYに代入

        }

        return x; // 余りが0になった時の除数が最大公約数

    }

}

3. アルゴリズムの挙動を追う

$X = 1071, Y = 1029$ の場合の計算推移をシミュレーションしてみます。

÷ 1029 = 1 余り 42

÷ 42 = 24 余り 21

÷ 21 = 2 余り 0

$\rightarrow$ 余りが 0 になったため、その時の除数 21 が最大公約数！

桁数の大きな数字同士であっても、驚くほど少ないループ回数で答えに辿り着くことができます。

4. 【必見】Java標準ライブラリで一発解決！

アルゴリズムの自作ロジックを理解した上で押さえておきたいのが、Java標準ライブラリ java.math.BigInteger の存在です。

BigInteger.gcd() を使った実装例

import java.math.BigInteger;

public class GCDMain {

    public static void main(String[] args) {

        // valueOfを使用してBigIntegerインスタンスを作成

        BigInteger b1 = BigInteger.valueOf(1071);

        BigInteger b2 = BigInteger.valueOf(1029);



        // gcdメソッドを呼び出すだけ

        BigInteger gcd = b1.gcd(b2);



        System.out.println("最大公約数は: " + gcd); // 実行結果: 21

    }

}

【解説と補足ポイント：なぜ標準機能を知っておくべきなのか】

■ 1. 正確性と桁数上限の克服

long 型の範囲を超えるような極めて巨大な数値同士の計算でも、オーバーフローを起こさずに安全に処理できます。

■ 2. 堅牢性と最適化

内部で最適化されたアルゴリズムが採用されており、パフォーマンス・信頼性ともに非常に高く設計されています。

■ 3. 実務における「車輪の再発明」の防止

基本ロジックを理解した上で、実務開発では実績のある標準ライブラリを賢く活用するのがプロエンジニアのベストプラクティスです。

5. まとめ

・基本：「$X \div Y$ の余り」を次の除数にするループを回して最大公約数（GCD）を求める。

・応用：最大公約数（GCD）がわかれば、最小公倍数（LCM）は $(X \times Y) \div \text{GCD}$ で計算可能。

・Javaの実務テクニック：BigInteger.gcd() を使えば1行で確実に実装可能。

アルゴリズムの仕組みを知ることはプログラミングの「思考力」を鍛え、便利な標準機能を知ることは「生産性」を高めてくれます。両方のアプローチをバランスよく身につけていきましょう！

【PicoCTF】単層パーセプトロンの限界を暴け！「Perceptron Train XOR」の数理検証アプローチ

CyLab Security Academy（旧PicoCTF）の「AI」カテゴリにある問題「Perceptron Train XOR」に挑戦しました！

今回のテーマは機械学習の基礎である「単層パーセプトロンの学習限界」。非線形なXORデータに対し、重みの更新ルールがどう働き、どこで頭打ちになるのかを実際にパラメータを操作して検証したアプローチをまとめておきます。

1. 「Perceptron Train XOR」とはどんな問題？

問題文とルールを確認します。

・カテゴリ： AI / Machine Learning（難易度：Easy）

・問題文： 「Watch a perceptron learn in real time on XOR data using the classic update rule: only misclassified points trigger updates, with no weight decay. Because XOR is not linearly separable, a single perceptron cannot hit 100% accuracy. Reach 75% accuracy to prove you understand the limitation and reveal the flag.」

・ヒント・制約： 誤分類された点のみが重みの更新を引き起こし、重み減衰はない。XORは線形分離不可能なため単一パーセプトロンでは100%に到達せず、目標である75%の精度に到達することがクリア条件となる。

XOR（排他的論理和）は直線を1本引くだけでは綺麗に分類できない「非線形分離不可能」なデータセットです。そのため、単層のパーセプトロンでは理論上100%正解することができず、4点中3点が正解となる75%の精度がモデルの限界点となります。

2. パラメータの確認とトレーニングの実行プロセス

ブラウザ上でインスタンスを立ち上げ、以下の手順で挙動を検証します。

1. 学習率（Learning Rate）の設定

Learning rate: 0.02 (デフォルト値)

初期パラメータとして設定されている学習率を確認し、モデルがどのように重みを更新していくかのベースラインを置きます。
2. トレーニングの実行と精度の収束確認

Status: Target accuracy (75%) reached.

「Run training」を実行し、誤分類されたデータポイントトリガーによる重み・バイアスのリアルタイム更新を追跡。非線形分離の構造的限界により、数ステップで精度の頭打ち（75%）に到達することを確認します。

【解法のポイント】
「アルゴリズムの数理的限界（非線形分離の不可能性）を理解しているか」がそのままクリア条件に直結している点が秀逸です。単にコードを動かすだけでなく、モデルがどこで失敗し、なぜそれ以上精度が上がらないのかという「制約のメカニズム」を把握することが本質的な攻略アプローチとなります。

3. まとめ

・単層パーセプトロンにおけるXOR問題の非線形分離の限界と、誤分類ベースの重み更新ルールをハンズオン形式で検証

・デフォルトの学習率（0.02）を用いたトレーニングにより、理論上の限界値である75%の精度に到達することを確認

・機械学習モデルの構造的制約を理論と実機の両面から理解・証明するプロセスとしての重要性

インフラやWebの脆弱性だけでなく、AI・機械学習の数理モデルの制約検証まで一貫したプロセスでドキュメント化できるのは非常に価値があります。次回のチャレンジもこの検証スタイルを貫いて攻略を進めていきます！

【PicoCTF】複数の命令で扉を開け！「ping-cmd」のコマンドインジェクションアプローチ

前回に続き、愛用のM3 MacBook Airのターミナルを相棒に、CyLab Security Academy（旧PicoCTF）の「Web Exploitation」または「General Skills」カテゴリにある問題「ping-cmd」に挑戦しました！

今回の問題は、入力値の検証の隙を突く**「OSコマンドインジェクション」**がテーマ。どのようなヒントから脆弱性を見抜き、複数の命令を組み立てていったのか、そのアプローチをまとめておきます。

1. 「ping-cmd」とはどんな問題？

問題文とヒントを見ると、次のように書かれています。

・カテゴリ： Web Exploitation / General Skills（難易度：Easy）

・問題文： 「Can you make the server reveal its secrets? It seems to be able to ping Google DNS, but what happens if you get a little creative with your input?（サーバーに秘密を明かさせることができますか？Google DNSにpingを飛ばせるようですが、入力をちょっと工夫するとどうなるでしょうか？）」

・ヒント： 「OSのコマンドとして実行します」「一度に複数の命令出してみて」

Netcat（nc）で接続する対話型インターフェースになっており、IPアドレスの入力を求められますが、制限として「8.8.8.8しか許可していない」と表示されます。しかし、ヒントにある「OSコマンドとしての実行」や「一度に複数の命令を出す」というキーワードが、今回の最大の攻略の糸口になります。

2. 2つのステップでコマンドインジェクションを仕掛ける

M3 MacBook AirのターミナルからNetcatでサーバーに接続し、シェル文字を用いた入力の工夫を試みます。

1. 区切り文字を用いたファイル構造の偵察

8.8.8.8; ls

許可されているIPアドレスの後にセミコロン（;）を挟んで別のコマンドを連結し、サーバー内部のファイル一覧（flag.txt など）を確認します。
2. ターゲットファイルの読み込み

8.8.8.8; cat flag.txt

同様にコマンドセパレータを活用して、見つけたフラグファイルの中身を標準出力へ強制的に吐き出させます。

【ポイント】
「複数の命令を一度に出す」というヒント通りにコマンドの区切り文字を利用することで、制限された入力をすり抜けて任意のシステムコマンドを実行できるのが、OSコマンドインジェクションの恐ろしさであり、パズルとしての醍醐味ですね！

3. まとめ

・「ping-cmd」は、入力値がそのままOSのシェルへ渡される脆弱性を突き、コマンドの連続実行によって目的を果たす問題

・「一度に複数の命令を出す」というヒントから、セミコロン等の区切り文字を活用する発想が重要

・問題文やヒントの行間を読み解き、想定された脆弱性アプローチを綺麗にハマらせたときの快感は格別！

入力値のバリデーションの裏側にある仕組みを想像しながら、ターミナルから一撃で攻略できると本当に気持ちが良いですね。次回のチャレンジもコマンドラインを武器に華麗に攻略していきたいと思います！