【アルゴリズム】メモリの自動掃除屋！「ガベージコレクション」｜情報処理問題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大スターです。データの特性に合わせてこれらを使いこなすことが、プログラムの高速化への第一歩となります。