# 問題解決力を鍛える！アルゴリズムとデータ構造
https://github.com/drken1215/book_algorithm_solution

## 第3章

- 任意参加
- ファシリテーター: 許

### 話す・書く順番決めルーレット

in Ruby

['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }

in JavaScript

const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]

### ファシリテーター決め方

- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく

### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）

当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分

### 勉強会時にやること

各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め

## 各自が書き込む場所

> [name=Chen]

#### 3.1 全探索 (1)：線形探索法ーO(N)
めっちゃめっちゃ使っているやつと思います
配列の値を探す、判断する、計算するなどの定番。

#### 3.2 全探索 (2)：ペアの全探索ーO(N^2)
二重forループのアルゴリズム。
お二つの配列を比較し、または計算する時によく使っている。

#### 3.3 全探索 (3)：組合せの全探索 (*)ーO(N2^N)
> N 個の整数からなる集合の部分集合は 2^N 通りあります。…それらを全探索する方法です。

N の集合 {a0, a1, ..., aN－1} の部分集合をすべて走査できる方法で、
初めて知りました。
が、二進法表現とビット演算は少し理解しにくい...:thinking_face:

> [name=teruya]

> 探索中にvが見つかったら探索を打ち切ってbreakする ... しかしこの工夫を施しても、計算量のオーダーという意味でのアルゴリズムの良さは変わりません(p.74)

Array#find

> code3.6 部分和問題に対するビットを用いる全探索解法

n, w = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

exist = false

# n = 3の時、 bit は 0(000), 1(001), 2(010) ... 7(111) までの 8 通り
(2 ** n).times do |bit|
  sum = 0
  # n = 3の時はbitを3つ調べる
  n.times do |i|
    # bit が 6(110) の時、bit[0]は0、bit[1]は1、bit[2]は1
    sum += nums[i] if bit[i] == 1
  end
  exist = true if sum == w
end
puts exist

n, w = gets.split.map(&:to_i)
nums = gets.split.map(&:to_i)

exist = false

(1..n).each do |i|
  # [1, 3, 5].combination(2) は [1, 3], [1, 5], [3, 5]がselected_numsに渡る
  nums.combination(i) do |selected_nums|
    exist = true if selected_nums.sum == w
  end
end
puts exist

> 3.5 N個の正の整数...

https://atcoder.jp/contests/abc051/submissions/6941239
O(N^3) を O(N^2) に落とす問題
（例えば0〜100の中から3回選んで合計250を作りたいとして、
1つ目100,2つ目200の時に、3つ目は全探索しなくても0を選べば200、100を選べば300なんだから
その間の250も作れるはずじゃない？みたいな感じ）

> [name=hsu]

3.3 find_id

const ＬinerSearch = (arr, x) => {
for (i = 0; i < arr.length; i++) {
    if (arr[i] === x) return i;
  }
  return -1;
};

best : O(1)?
worse: O(N)

3.3.2 find_minValue

const FindMinValueByLinerSearch = (arr) => {
  let minValue = arr[0]
  for (i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) minValue = arr[i]
  }
  return minValue
};

best : O(1)?
worse: O(N)

average: O(N / 2) でも、1/2は誤差なので取り除く、なので結局O(N)
例えばN = 1,000,000 の時, N * 2 = 2,000,000 N / 2 = 500,000
N * N = 1,000,000,000,000
worst: O(N)

3.6 c++のcodeわからない...

int N, W;
cin >> N >> W;
vector<int> a(N);
for (int i = 0; i < N; ++i) cin >> a[i]; ここはなんだろう？

'>>' 入力、アサイン
'<<' 出力

> [name=okura]

### 3.1 全探索を学ぶ意義

一番基本だから、ということですね。

### 3.2 全探索(1)：線形探索法

いつも最初に思いついて、だいたいうまくいかない（時間がかかりすぎる）やつ。

### 3.3 線形探索法の応用

探索プログラムが状態を持っている、ということで、その「状態」に何を格納しておくかを変えることで目的に応じた探索が可能。

### 3.4 全探索(2)：ペアの全探索

> なお，実はこの問題は二分探索法を用いることで，O(NlogN)で解くこともできます

それはすごい。

### 3.5 全探索(3)：組み合わせの全探索

探索の対象全てをビットとして表現するというのはなるほどという感じ。最初にあり得る組み合わせを全部出しておくことで解法を単純化できるのだと思う。

### 章末問題

解けてない…

## 振り返り

> [name=hsu]

普段linerSearch書いてますが、実際あまり意識してなかった。。。二重loop使わないように意識していきます。

> [name=teruya]

取り得る値がbooleanの2値の時に、bitを使って管理したら簡単やん！って思いついた人すごい。
（けどすごすぎて日常ではあまり馴染みがない）

とりあえず配列がunsortedの時はO(NlogN)でソートしてから考えるみたいなのはよくあります😂

> [name=chen]

ビット演算はマジで難しい...アルゴリズム力不足:cry:

> [name=okura]

「これ、対象がソート済みだったらなあ」→「ソートすればいいのでは？？？」みたいな。

## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- Chenさん
- 読む範囲を決める
- 第4.3章まで