【超初心者向け】全探索のきほんのき【C++】

はじめに

アルゴリズムを学ぶ上で、重要なのが、全探索という考え方です。

探索は、データの集合の中から目的の要素を探すことです。問題について、考えられる可能性をすべて調べることで、正解を導きます。

3桁のダイヤル式の南京錠を開けるとき、000 から 999 までのすべての番号を試せば、開けることができます。

• 000 で開くか試す

• ダメなら、001 で開くか試す

• ダメなら、002 で開くか試す

• ダメなら、003 で開くか試す

• 開くまでこれを繰り返していく（最大 999 まで）

このように、ありえるパターンをすべて試すのが全探索です。

対象読者

• プログラミング初心者で、競技プログラミングを始めてみたい人

• C++ について勉強したい人

この記事では、プログラミング初心者の方に向けてやさしく解説しています。

線形探索

探索の方法としての1つである、線形探索について説明します。

線形探索は、データの集合について1つずつ順番に目的のものかどうかを調べていく方法です。

次の図は、10、20、30、40、50 の数字の中に 40 が含まれているか、数字を1つずつ順番に調べていく様子を表したものです。

1. 左から1番目の数字は 40 か？　10 なので違う

2. 左から2番目の数字は 40 か？　20 なので違う

3. 左から3番目の数字は 40 か？　30 なので違う

4. 左から4番目の数字は 40 か？　40 なので正解

5. 左から5番目の数字は 40 か？　50 なので違う

線形探索を学ぶために次の問題について考えてみます。競技プログラミングの鉄則の演習問題の1つです。

■問題文
N 個の整数 A₁, A₂, ・・・, Aₙ の中に、整数 X が含まれるかどうかを判定するプログラムを作成してください。

■制約
・1 ≦ N ≦ 100
・1 ≦ X ≦ 100
・1 ≦ A₁, A₂, ・・・, Aₙ ≦ 100

■入力
N X
A₁ A₂ ・・・ Aₙ

■出力
X が含まれるとき Yes 、含まれないとき No と出力

A02 - Linear Search - AtCoder（競技プログラミングの鉄則演習問題集）

この問題に対する C++ の解答コードです。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, X;
    cin >> N >> X;

    int A[N];
    for (int i = 0; i < N; i++) {
      cin >> A[i];
    }
 
    // 線形探索
    bool exist = false;
    for (int i = 0; i < N; i++) {
      if (A[i] == X)  exist = true;
    }
  
    // 出力
    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
  
    return 0;
}

競技プログラミングについて、わからない場合は次の記事を参考にしてください。

コードの解説

先ほどのコードについて解説していきます。

標準ライブラリと名前空間

まずは、以下の2行のコードです。このコードは、様々な機能をまとめた標準ライブラリの読み込みと、名前空間の宣言です。

// で始まる行はコメント行と言われ、プログラムの実行には関係しません。

#include <bits/stdc++.h>  // 標準ライブラリの読み込み
using namespace std;      // 名前空間の宣言

標準ライブラリを使うためには 「std::」を標準ライブラリの機能の前に書く必要がありますが、 名前空間を宣言することで、「 std:: 」を省略することができます。

main関数

C++ では、main() 関数がプログラミングの実行開始点です。この中に問題に解答するコードを書いていきます。

int main() {
    // 問題に解答するためのコード
}

これから、線形探索のメイン処理について見ていきます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, X;
    cin >> N >> X;

    int A[N];
    for (int i = 0; i < N; i++) {
      cin >> A[i];
    }
 
    // 線形探索
    bool exist = false;
    for (int i = 0; i < N; i++) {
      if (A[i] == X)  exist = true;
    }
  
    // 出力
    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
  
    return 0;
}

競技プログラミングでは、入力を受け取り、計算して、出力するという流れになります。

次のコードは、変数 N と X を宣言して、入力を受け取っています。入力の受け取りには cin を使います。

int N, X;
cin >> N >> X;

整数の集合の A₁, A₂, ・・・, Aₙは、配列で受け取ります。int A[N] で配列を宣言して、そのあとのコードで、入力を受け取っています。

int A[N];
for (int i = 0; i < N; i++) {
  cin >> A[i];
}

配列

配列は、複数のデータをまとめて格納できるので、関連のあるデータを管理するのに便利です。

配列は次のように宣言します。

型　変数名［サイズ］；

次のコードは、10 個の要素を持つ int 型の配列 array を宣言して、最初の要素に 5 を代入しています。

// 配列の宣言
int array[10];

// 最初の要素に値を代入
array[0] = 5;

解答コードでは、int 型でサイズが N の A という名前の配列を宣言しています。N は、入力として受け取る int 型の変数です。事前に入力として受け取っています。

例えば、N への入力が 5 だとすれば、int A[N] は int A[5] ということになります。

int A[N];  // N が 5 だとすれば int A[5]; となる

配列内のデータは順番に並んでいて、添え字（インデックス）を使ってデータを取り出します。

次のコードは、 1 から 5 までの値を持った array という配列を宣言しています。

// 配列の宣言
int array[5] = {1, 2, 3, 4, 5};

// 2つ目の要素の値を出力
cout << array[1];  // => 2

添え字は 0 から始まるので注意してください。

for

配列を宣言したあとに、for で入力を受け取っています。

int A[N];
for (int i = 0; i < N; i++) {
  cin >> A[i];
}

forを使えば、繰り返し処理をすることができます。

for は、次のように書きます。

for （初期設定部；　条件判定部；　インクリメント部）｛
　　処理；
｝

• 初期設定部：ループが始まる前に1度だけ実行されます。

• 条件判定部：条件が ture （真）の間はループが繰り返します。ループの先頭で実行されます。

• インクリメント部：ループの制御変数の値を一定量増やします。ループの末尾で実行されます。

次のコードでは、1 から 5 までの数字を出力します。/*　*/ はコメントを表します。/*　*/ で囲まれたところはコメントになります。
cout は出力で、endl は改行を表します。

#include <bits/stdc++.h>
using namespace std;

int main() {
  for (int i = 1; i < 6; i++) {
    cout << i << endl;
  }
  return 0;
}

/*
実行結果
1
2
3
4
5
*/

初期設定部「int i = 1;」は、int 型の i という変数に 1 を代入しています。

そのあとに、条件判定部の「i < 6;」 が実行されます。i は 1 なので、「1 < 6」となり、真と判定されるので for 内の処理が実行されます。

for 内の処理「cout << i << endl;」が実行されたら、インクリメント部「i++」が実行されます。i++ は i = i + 1 と同じ意味です。

現在 i は 1 なので i = 1 + 1 になり、i には 2 が代入されます。

これで1つのループが終わったので、条件判定部に戻ります。

条件判定部の i < 6 が実行されます。i は 2 なので、真と判定されるので for 内の処理が実行されます。

for 内の処理が実行されたら、インクリメント部が実行されます。現在 i は 2 なので i = 2 + 1 になり、i には 3 が代入されます。

これを繰り返し、i が 6 になると条件判定の i < 6 が偽になるので、ループが終了します。

以上をふまえて、整数の集合の A₁, A₂, ・・・, Aₙを、配列で受け取るコードを見てみましょう。

for (int i = 0; i < N; i++) {
  cin >> A[i];
}

N が 3 だったとして、考えてみます。

i に 0 が代入されます。条件判定部は、i < 3 なので、ループ内の処理が実行されます。
A[0] に入力が代入されます。その後、インクリメント部で i が 1 になります。

i は 1 なので、i < 3 は真になり、ループ内の処理で A[1] に入力が代入されます。

i が 2 になります。

i は 2 なので、i < 3 は真になり、ループ内の処理で A[2] に入力が代入されます。

i が 3 になります。

i は 3 なので、i < 3 は偽になるので、ループは終了します。

これで、A[0]、A[1]、A[2] に入力が代入されました。

線形探索

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, X;
    cin >> N >> X;

    int A[N];
    for (int i = 0; i < N; i++) {
      cin >> A[i];
    }
 
    // 線形探索
    bool exist = false;
    for (int i = 0; i < N; i++) {
      if (A[i] == X)  exist = true;
    }
  
    // 出力
    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
  
    return 0;
}

探索しているのが以下の部分です。

// 線形探索
bool exist = false;
for (int i = 0; i < N; i++) {
  if (A[i] == X)  exist = true;
}

bool exist = false; は、bool 型の exist という変数に false を代入しています。
bool 型は、true（真）とfalse（偽）のどちらかを持ちます。

整数 X が存在するか、存在しないかを管理する変数が exist です。

まだ、探索はしていないので X は存在していないと exist に false を代入しています。

次の for は 0 から N までの繰り返し処理です。この for で、入力されたすべての整数について処理しています。

for (int i = 0; i < N; i++) {
  if (A[i] == X)  exist = true;
}

ループの中の処理は if (A[i] == X)   exist = true;  です。

if文

if 文は、条件によって処理を分岐させたいときに使います。次のように使い、式が true（真）と判断されたときに、処理が実行されます。

if（式）処理；

if 文は、else と組み合わせて使うことができます。式が true（真）の時は処理１が実行され、式が false（偽）の時は処理２が実行されます。

if（式）処理１；
else　処理２；

複数の処理をしたいときには、｛｝を使います。

if（式）｛
　処理１ー１；
　処理１－２；
｝
else｛
　処理２ー１；
　処理２－２；
｝

次のコードはすべて　”ここは実行されます”　と書かれたところが実行されます。
値が等しいかどうかの判定は == で行います。=ではないことに注意して下さい。

#include <bits/stdc++.h>
using namespace std;

int main() {
  if (true)  cout << "ここは実行されます"    << endl;
  if (false) cout << "ここは実行されません"  << endl;

  if (5 < 10) cout << "ここは実行されます"   << endl;
  if (2 == 3) cout << "ここは実行されません" << endl;
  
  if (3 > 4)  cout << "ここは実行されません" << endl;
  else        cout << "ここは実行されます"   << endl;
  
  if (2 == 2) {
    cout << "ここは";
    cout << "実行";
    cout << "されます";
  }
  
  return 0;
}

/*
実行結果
ここは実行されます
ここは実行されます
ここは実行されます
ここは実行されます
*/

次のコードは、入力された整数を1つずつ確認して、配列に代入されている整数が X のとき、変数 exist に true（真）を代入しています。 

for (int i = 0; i < N; i++) {
  if (A[i] == X)  exist = true;
}

出力

線形探索で、整数すべてについて X と等しいか判定しました。
X と等しい整数があった場合は、if 文の exist = true; が実行されます。すべての整数が X と違うときは、if文の exist = true; が実行されないため、exist は初期値の false のままです。

• X があったときは exist = true

• X がなかったときは exist = false

if 文を使って exist の値によって分岐させて、出力させる文字列を変えています。

// 出力
if (exist) cout << "Yes" << endl;
else cout << "No" << endl;

exist が true のとき（X が含まれているとき）は、cout << "Yes" << endl; が実行されます。
それ以外の値のとき（X が含まれていないとき）は、cout << "No" << endl; が実行されます。

まとめ

解答コードを再び見てみます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力
    int N, X;
    cin >> N >> X;

    int A[N];
    for (int i = 0; i < N; i++) {
      cin >> A[i];
    }
 
    // 全探索
    bool exist = false;
    for (int i = 0; i < N; i++) {
      if (A[i] == X)  exist = true;
    }
  
    // 出力
    if (exist) cout << "Yes" << endl;
    else cout << "No" << endl;
  
    return 0;
}

cin で、整数の個数 N と、調べる整数 X を受け取っています。
その後、探索する整数を配列に入力していきます。

// 入力
int N, X;
cin >> N >> X;

int A[N];
for (int i = 0; i < N; i++) {
  cin >> A[i];
}

入力の受け取りが終われば、探索の開始です。
まずは、整数 X があったかどうかを管理する bool 型の exist 変数を宣言します。
そして、配列 A の整数について、1つずつ順番に X かどうかを判定し、もし X ならば exist に true を代入します。

// 線形探索
bool exist = false;
for (int i = 0; i < N; i++) {
  if (A[i] == X)  exist = true;
}

最後に、X があったかどうかを exist の値によって判定し、cout で文字列を出力しています。

// 出力
if (exist) cout << "Yes" << endl;
else cout << "No" << endl;

全探索は競技プログラミングにおいて重要なものです。しっかり習得しましょう。

プログラミングの経験はあるが、C++ は初めてという方に向けての記事も書いています。

【競プロ】AtCoderを始めるためのC++の基本

過去問を解くのがおすすめです。素晴らしいサイトがあります。AtCoder の過去問をレベル別に並び替えたりすることができます。

AtCoder Problems

書籍では、アルゴリズムなどの知識を体系的に学ぶことができるのでお勧めです。

問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本

競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~ (Compass Booksシリーズ)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～