【共通】1. テクノロジ系＞1-1. 基礎理論＞1-1-2. アルゴリズム｜情報処理問題1000本ノック

【データ構造】積み上げる動作！スタックの「プッシュ」｜情報処理問題1000本ノック

スタック構造において、データを格納する基本アクションを正しく理解しましょう。

1. 問題：スタックへの追加操作

【問題】 データ構造の一つである「スタック（stack）」において、新しいオブジェクト（データ）をデータ構造の末尾（一番上）に追加する操作を何と呼ぶでしょうか？

① プッシュ（Push） ② ポップ（Pop） ③ プット（Put） ④ ゲット（Get）

2. 正解：データ構造の操作に関する正解

正解： ① プッシュ（Push）

3. 解説：スタック（積まれた本）の世界

スタックは「積み重ね」を意味します。新しいデータを置くときは、常に既存のデータの上に重ねていきます。

【図解：プッシュ操作のイメージ】

■ プッシュ（Push = 押し込む）

・空の箱に下から順番にデータを詰めていくイメージです。

・最後に追加したデータが、常に「一番上（TOP）」に位置します。

■ 特徴

・データを追加する場所を選ぶことはできません。常に「末尾（一番上）」への追加となります。

[ 現場での使われ方 ]

★ プログラムが関数を呼び出す際、現在の処理の状態を一時的に保存するためにスタックが使われます。これを「スタックに積む」や「プッシュする」と表現します。

1. 理解のコツ: 筒状の容器にテニスボールを押し込んでいく様子を想像してください。ボールを入れる動作が「プッシュ」です。最初に入れたボールは底に沈み、後から入れたボールが取り出しやすい位置に来ます。
2. 試験対策の視点: 「LIFO（Last-In First-Out：後入れ先出し）」という言葉とセットで、「プッシュした順序の逆でポップされる」というデータの流れを把握しておくことが重要です。

4. まとめ

「スタックにデータを追加する操作」。これがプッシュ（Push）です。取り出しの「ポップ」と対になる、コンピュータ科学における最も基礎的な操作の一つです。

【データ構造】最後に入れたものを最初に出す！「スタック」｜情報処理問題1000本ノック

データの出し入れに制限を設けることで、処理の順序を効率的に管理する「スタック」。プログラミングやCPUの処理でも多用されるこの構造を攻略しましょう。

1. 問題：スタックからの取り出し操作

【問題】 データ構造の一つである「スタック（stack）」において、スタックの先頭（最後に入れた場所）からオブジェクトを取り出す操作を何と呼ぶでしょうか？

① プッシュ（Push） ② ポップ（Pop） ③ プット（Put） ④ ゲット（Get）

2. 正解：データ構造の操作に関する正解

正解： ② ポップ（Pop）

3. 解説：LIFO（後入れ先出し）の仕組み

スタックは、データの入り口と出口が同じ場所にあるデータ構造です。この性質を「LIFO（Last-In, First-Out）」と呼びます。

【図解：スタックの2大操作】

■ プッシュ（Push）

・データをスタックの「一番上」に積み上げる（挿入する）操作。

■ ポップ（Pop）

・スタックの「一番上」にあるデータを一つ取り出す操作。

★ 性質：後入れ先出し（LIFO）

・1番目に入れたデータは、2番目・3番目のデータが取り出されるまで、絶対に取り出すことができません。

[ 比較して覚えたい：キュー（Queue） ]

★ キュー：入り口と出口が反対側にある構造（レジの行列と同じ）。

★ FIFO (First-In, First-Out)：最初に入れたものが最初に出てくる。この時の操作は「エンキュー（入れる）」「デキュー（出す）」と呼びます。

1. 理解のコツ: 机の上に積み上げられた本をイメージしてください。新しく置くときは「一番上（プッシュ）」に置き、読むために取るときも「一番上（ポップ）」から取りますよね。一番下の本を取ろうとすると崩れてしまいます。
2. 試験対策の視点: 「LIFO（後入れ先出し）」という言葉とセットで出題されます。また、関数の呼び出し履歴（コールスタック）や、数式の逆ポーランド記法などの計算問題でも、このポップ操作が鍵となります。

4. まとめ

「スタックの先頭からデータを取り出す操作」。これがポップ（Pop）です。入れるときはプッシュ、出すときはポップ。この一対の動きが、複雑なプログラムの実行順序を支えています。

【アルゴリズム】バグを減らす設計の極意！「関数の参照透過性」｜情報処理

プログラムの動作を予測しやすくし、テストや並列処理を容易にする「参照透過性」という概念があります。数学的な関数に近い、そのクリーンな性質を攻略しましょう。

1. 問題：関数の参照透過性の定義

【問題】 プログラミングにおける「関数の参照透過性」を説明したものとして、最も適切なものはどれでしょうか？

ア、関数が自分自身を再帰的に呼び出すことができる性質
イ、同じ引数に対しては常に同じ結果を返し、かつ外部の状態に影響を与えない性質
ウ、関数の引数として、別の関数を渡すことができる性質
エ、関数内部からグローバル変数に自由にアクセスし、書き換えができる性質

2. 正解：プログラミング理論に関する正解

正解：イ、同じ引数に対しては常に同じ結果を返し、かつ外部の状態に影響を与えない性質

3. 解説：「置き換え可能」であることの価値

参照透過性（Referential Transparency）とは、ある関数呼び出しを「その実行結果の値」に置き換えても、プログラムの意味が変わらないことを指します。

【図解：参照透過な関数（純粋関数）の条件】

■ 副作用がない (No Side Effects)

・関数の外にある変数を書き換えない。

・画面出力やファイル書き込みを行わない。

■ 入力のみに依存する

・現在時刻や乱数、外部ファイルの内容など、呼び出すたびに変わるものに依存しない。

■ 例： add(2, 3) 

・いつどこで実行しても必ず「5」を返す。このため、コード中の `add(2, 3)` を直接 `5` と書いてもプログラムの結果は同じになる。

[ 参照透過性のメリット ]

★ メモ化が可能：一度計算した結果を再利用できるため、パフォーマンス向上に寄与する。

★ テストが容易：外部の状態を準備（モック化）する必要がなく、引数だけでテストが完結する。

★ スレッド安全：共有データを書き換えないため、マルチスレッド環境でも安全に動作する。

1. 理解のコツ: 「数学の関数（$y = f(x)$）」をイメージしてください。数学では同じ $x$ を入れれば必ず同じ $y$ が出ますし、計算したからといってノートの別の場所の数字が変わることもありません。これが参照透過な状態です。
2. 試験対策の視点: 関数型プログラミングの文脈でよく出題されます。「副作用がない」「引数だけで結果が決まる」というフレーズがキーワードです。対照的な概念として「非純粋関数」もセットで覚えておきましょう。

4. まとめ

「同じ入力なら同じ出力、副作用なし」。これが関数の参照透過性です。全ての関数を参照透過にすることは難しいですが、可能な限りこの性質を持たせることで、堅牢でメンテナンスしやすいシステムを構築できます。

【アルゴリズム】素数をあぶり出す！「エラトステネスのふるい」｜情報処理問題1000本ノック

プログラミングの基礎問題としても頻出の「素数判定」。その中でも、特定の範囲から素数をまとめて探し出す効率的なアルゴリズムを攻略しましょう。

1. 問題：素数抽出のアルゴリズム

【問題】 指定された整数以下のすべての素数を効率的に見つけるための手法で、2から順にその倍数を消去していく（ふるい落とす）ことで素数だけを残すアルゴリズムを何と呼ぶでしょうか？

ア、エラトステネスのふるいイ、遺伝的アルゴリズムウ、アリストテレスのアルゴリズムエ、ピタゴラスの定理

2. 正解：アルゴリズムの基礎に関する正解

正解：ア、エラトステネスのふるい

3. 解説：倍数を消して素数を残す

エラトステネスのふるいは、紀元前3世紀にギリシャの数学者エラトステネスが考案した、非常にシンプルで高速な素数抽出法です。

【図解：エラトステネスのふるいの手順】

1. 初期状態

・2から目的の数（例：30）までの整数を並べます。

2. 倍数の消去

・「2」は素数として残し、2の倍数（4, 6, 8...）をすべて消します。

・次に残っている最小の数「3」を素数とし、3の倍数（9, 12...）を消します。

・これを繰り返し、最後に残ったものがすべて素数となります。

3. 終了条件

・探索する範囲の最大値の平方根（√n）まで調べれば、すべての素数が確定します。

[ 関連用語の整理 ]

★ 計算量：一つ一つ素数判定を行うより圧倒的に速く、O(n log log n)という非常に優れた効率を誇ります。

★ 遺伝的アルゴリズム：生物の進化を模倣して最適解を探る手法であり、素数判定とは無関係です。

★ 素数：1とその数自身でしか割り切れない、1より大きい自然数。

1. 理解のコツ: 「倍数は素数ではない」という性質を利用して、まるで「ふるい」にかけるように不純物（合成数）を取り除いていくイメージです。名前が似ている「アリストテレス（哲学者）」などに惑わされないようにしましょう。
2. 試験対策の視点: アルゴリズムの名称だけでなく、その具体的な手順（倍数を消していく）や効率性について問われることもあります。プログラミング試験でも実装例としてよく取り上げられるテーマです。

4. まとめ

「2から順に倍数を消去し、素数を抽出する」。これがエラトステネスのふるいです。数千年前の知恵が、現代のコンピュータ・プログラムにおいても現役で使われている非常に重要なアルゴリズムであることを押さえておきましょう。

【アルゴリズム】メモリの自動掃除屋！「ガベージコレクション」｜情報処理問題1000本ノック

プログラムを実行するとメモリ（ヒープ領域）を消費しますが、使い終わった領域をそのままにするとメモリ不足に陥ります。これを自動で解決する「ガベージコレクション」を攻略しましょう。

1. 問題：メモリの自動解放機構

【問題】 プログラムが動的に確保したメモリ領域のうち、不要になった（どこからも参照されなくなった）領域を自動的に検出し、解放して再利用可能にする機構を何と呼ぶでしょうか？

ア、メモリリークイ、ガベージコレクションウ、フラグメンテーションエ、ページング

2. 正解：メモリ管理に関する正解

正解：イ、ガベージコレクション

3. 解説：ゴミ（Garbage）を回収（Collection）する

ガベージコレクション（GC）は、プログラマが明示的にメモリ解放のコードを書かなくても、実行環境が裏側で不要なメモリを掃除してくれる画期的な仕組みです。

【図解：ガベージコレクションの役割】

1. メモリの確保

・プログラムが新しいデータを作る際、メモリを「動的」に確保します。

2. 参照の喪失

・そのデータを使わなくなり、どの変数からもアクセスできなくなると「ゴミ（Garbage）」になります。

3. 自動解放

・GCが定期的に「ゴミ」を見つけ出し、メモリを空き状態に戻します。

[ メモリ関連の重要用語 ]

★ メモリリーク：解放すべきメモリが放置され、空きメモリが減り続ける現象。GCがない言語（C言語など）で発生しやすい不具合です。

★ フラグメンテーション：メモリの空き領域が細切れになり、大きなデータが格納できなくなる「断片化」現象。

★ コンパクション：断片化したメモリを整理整頓して、連続した空き領域を作る作業（GCの一部として行われることが多い）。

1. 理解のコツ: 昔のプログラミング（C言語など）では「借りたものは自分で返す（free）」のがルールでしたが、返し忘れるミスが多発しました。ガベージコレクションは「ホテルの清掃員」のように、客がチェックアウト（参照終了）した後に自動で部屋を片付けてくれるサービスだとイメージしてください。
2. 試験対策の視点: アルゴリズムやプログラミングの基礎として頻出です。特に「Java」などのモダンな言語では標準機能であること、またGC実行中にはプログラムが一瞬止まる（Stop The World）といった特性があることも併せて知っておくと完璧です。

4. まとめ

「不要なメモリ領域を自動的に開放する」。これがガベージコレクションです。開発者がメモリ管理の苦労から解放され、本来のロジック開発に集中できるようにするための重要な技術であることを押さえておきましょう！

【アルゴリズム】目的のデータを探せ！「3つの探索アルゴリズム」比較｜情報処理問題1000本ノック

大量のデータの中から、目的の値を効率よく見つけ出す「探索（サーチ）」。データの状態や量に応じて、最適な手法を選択することがアルゴリズムの基本です。

1. 問題：効率的な探索手法の選択

【問題】 あらかじめ昇順または降順に並べ替えられた（ソート済み）データ群に対して、中央の値と比較して探索範囲を半分に絞り込んでいく手法を何と呼ぶでしょうか？

① リニアサーチ（線形探索） ② バイナリサーチ（二分探索） ③ ハッシュサーチ ④ 木探索

2. 正解：探索アルゴリズムに関する正解

正解： ② バイナリサーチ（二分探索）

3. 解説：計算量（オーダー）と仕組みの整理

探索アルゴリズムは、データの並び方や「どれだけ速く見つけられるか（計算量）」によって使い分けます。試験頻出の3手法をマスターしましょう。

【図解：探索手法の比較表】

■ リニアサーチ（線形探索）

・仕組み：先頭から順番に1つずつ比較する。

・条件：データの並び順は問わない。

・計算量：O(n)（データ量に比例して時間がかかる）

■ バイナリサーチ（二分探索）

・仕組み：中央の値と比較し、範囲を半分ずつに絞る。

・条件：データがソート（整列）済みであること。

・計算量：O(\log_2 n)（データが増えても時間はあまり増えない）

■ ハッシュサーチ

・仕組み：ハッシュ関数を用いて、データの格納場所を一発で特定する。

・条件：ハッシュテーブルを作成しておく必要がある。

・計算量：O(1)（データ量に関わらず、ほぼ一定の時間）

[ 関連用語の整理 ]

★ オーダー (O)：アルゴリズムの効率性を示す指標。小さいほど高速。

★ ハッシュ衝突（コリジョン）：異なるキーから同じハッシュ値が生成されてしまうこと。

★ 基本交換法（バブルソート）：探索の前準備として行われる代表的なソート手法。

1. 理解のコツ: 辞書を1ページ目からめくるのが「リニア」、真ん中でバサッと開いて前後を絞り込むのが「バイナリ」、索引（インデックス）でページを直接開くのが「ハッシュ」というイメージです。
2. 試験対策の視点: 「ソート済み」という前提条件があればバイナリサーチを疑いましょう。また、計算量のオーダー（O(1) < O(\log n) < O(n)）の大小関係も、計算問題や比較問題として非常によく出題されます。

4. まとめ

「単純なリニア、速いバイナリ、一瞬のハッシュ」。これが探索アルゴリズムの3大スターです。データの特性に合わせてこれらを使いこなすことが、プログラムの高速化への第一歩となります。