[AtCoder]線形探索法を理解する#C++

はじめに

---

こんにちは。
Atcoderを始めて約2週間のTokuです。
今回は『問題解決力を鍛える！アルゴリズムとデータ構造』から第３章設計技法(1)：全探索とアルゴ式 (algo-method.com)のアルゴリズム入門: 全探索を見ながら、基本的なアルゴリズムである線形探索法を理解してみました。
この記事に記載している問題は、『問題解決力を鍛える！アルゴリズムとデータ構造』から第３章設計技法(1)：全探索の問題とアルゴ式 (algo-method.com)のアルゴリズム入門: 全探索から多く参照しました。
本とサイトは、以下に掲載しています。
『問題解決力を鍛える！アルゴリズムとデータ構造』から第３章設計技法(1)：全探索

問題解決力を鍛える！アルゴリズムとデータ構造

アルゴ式 (algo-method.com)のアルゴリズム入門: 全探索

トピック一覧 | アルゴ式(beta)

線形探索法とは

---

線形探索法とは、データ構造内の各要素を順番に確認し、特定の値を探し出す最も基本的な探索アルゴリズムです。リストや配列などのデータ構造において、始めから終わりまで順にデータを調べて特定の値を見つける方法になります。
線形探索法の長所は、コードが簡単で理解しやすく、ソートされていないデータにもそのまま使えることです。そして、短所は、生産性や効率性が低いことがあります。例えば、データの量が数指数関数的に増加すると、計算時間が非常に長くなることがあります。

実際に、線形探索法(Linear Search Method)についてみていきます。
『問題解決力を鍛える！アルゴリズムとデータ構造』のpp.67-68から、線形探索法とは「１つ１つの要素を調べていく」とあり、基本的な探索問題は以下のように定式化されるとあります。

N個の整数a_0, a_1,...a_{n-1}と整数値vが与えられます。 a_i=vとなるデータが存在するのかどうかを判定してください。

『問題解決力を鍛える！アルゴリズムとデータ構造』pp.67-68

例えば、５つの整数a=(6, 7, 22, 3, 5)の中に、v=7が含まれるかどうかを線形探索法を用いて判定することができます。
線形探索法の手順は、
①aの整数を前から順番に調べていく
②調べた中にvがあれば、変数に情報を保持し、真偽値を保存する
となります。
以下、実装したコードになります。

#include <iostream>
#include <vector>
using namespace std;

int main(){
//入力を受け取る
	int N, v;
	cin >> N >> V;
	vector<int> a(N);
	for (int i = 0; i < N; ++i) cin >> a[i];
//線形探索
	bool flag = false;
	for(int i = 0; i < N; ++i){
			if(a[i] == v){
					flag = true;
			}
	}
//結果
	if(flag) cout << "Yes" << endl;
	else cout << "No" << endl;
}

コードの中の処理は、①入力を受け取る②線形探索③結果を出力の順番に書かれています。 計算量は②線形探索の部分において、N個の値を順番に調べているので最悪かかる時間はO(N)になります。 線形探索法の内容と手順を理解したところで、いくつかの問題を解いてみます。

最小値問題
最小値を求める問題を解いてみます。 アルゴリズムの手順について、以下のように実装します。 ①aの整数を前から順番に調べていく ②調べた中に最小値があれば、変数に情報を保持する この変数には「これまでの最も小さい値」を必ず保持できるように設定します。

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int N;
	cin >> N;
	vector<int> A(N);
	for(int i = 0; i < N; ++i) cin >> a[i];
	
	int min_num = 200000; //十分大きな値を入れる
	for(int i = 0; i < N; ++i){
			if(a[i] < min_num) min_num = A[i];
	}
	cout << min_num << endl;
}

素数判定問題
与えられた数字が素数かどうかを判定する問題を解いてみます。
素数の条件について、
条件１:１は素数に含めない
条件２: 1とN以外の約数を持つとき、Nは素数ではない
この２つの条件をもとに、以下のように実装します。
①１かどうかを判定する
②約数で割り、余りを調べる

#include <iostream>
using namespace std;

int main() {
    int N; 
    cin >> N;   
    if (N == 1) {
        cout << "No" << endl;
        return 0;
    }   
    bool is_prime = true;  
    for (int i = 2; i <= N-1; ++i) { 
        if (N % i == 0) { 
            is_prime = false; 
        }
    }
    if (is_prime) 
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;
}

最後に

---

線形探索法は「１つ１つの要素を順番に調べていく」という探索法でした。

その他

---

C＋＋の文法については、下記の動画とサイトから学びました。
ゼロから学ぶ C++
はじめてのC++！完全入門【HelloWorld~ポインタまで徹底解説】