LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Y-Kitano_saison

Golang 学習メモWeek4

Posted at

前回までのあらすじ

基本文法は大体把握した。
アルゴリズム系の学習が必要。
PaizaのAランクは普通に難しい。

今週の学習内用

1. アルゴリズム 尺取法

数列に対する区間を求める際に利用できるアルゴリズムで$O(n^2)$を$O(n)$に減らせることができる。
数列$a_1,a_2,...,a_n$から条件を満たす区間を調べるという課題に直面した時、全探索でやろうとすると計算量は$O(n^2)$になり、数列のサイズが大きくなるほど処理時間が膨大になってしまう。

尺取法では2つのポインタをしゃくとり虫のように移動させる形で区間を計算できる。
たとえば区間和を求める際等、区間和が条件を満たさないならポインタAを1つ動かし区間を広げる。
逆に満たすならポインタBを1つ動かし区間を狭める。
といったように、ポインタだけを動かすので計算量が$O(n)$で済み、処理時間を抑えられる。

下記は特定の値以上となる区間和を求める際、最短の区間長はどうなるかを尺取法で求める際の例。

main.go
func SyakutoriMethodMin(list []int, checkVal int) int {
	head, tail := 0, 0
	sum, ans := 0, len(list)+1
	for {
		// 区間の和が条件値を超えた場合
		if sum >= checkVal {
			// 条件を満たしているので、現在の長さと超えた瞬間の長さを比較
			ans = min(ans, head-tail)
			sum -= list[tail]
			tail += 1
		} else {
			if head == len(list) {
				break
			}
			sum += list[head]
			head += 1
		}
	}
	// 区間長が配列全体のままなら条件を満たせていない
	if ans == len(list)+1 {
		ans = -1
	}
	return ans
}

しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

2. アルゴリズム いもす法

累積和のアルゴリズムを多次元・多次数で行える手法

例： 配列Listの区間$l-r$にだけ加算を行いたい

①準備した差分配列の始点$l$に加算した値、終点$r$の次の要素$r+1$に対して減算した値を格納
②差分配列の累積和ともとの配列で計算を行う。
という流れで処理される。

いもす法で終点の次の要素に減算した値を格納する理由

いもす法では差分配列の累積和ともとの配列で計算を行う。
そのため累積和を求める際に終点の次の要素で減算することで、要素$n$の変更は終点以後で続かなくなる。
（ここの理解ができればいもす法はわかりやすいかも！）

下記例は数列$a_1,a_2...,a_n$の特定区間にのみ加算したいときの処理。Paizaでの提出した回答そのままなのでコードはちょっとわかりにくいかも。

main.go
// 長さNの加算用リストを作成
for i := 0; i < N+1; i++ {
    addList = append(addList, 0)
}
// 1. 特定区間に加算する値を記録
// 1 <= l <= u <= n として始点は -1 
for i := 0; i < M; i++ {
    fmt.Scanf("%d %d %d ", &l, &u, &a)
    // 区間始点に加算
    addList[l-1] += a
    // 区間終点に減算
    if u < N {
        addList[u] -= a
    }
}
// 加算結果を出力
for i := 0; i < N; i++ {
    fmt.Println(list[i] + addList[i])
    // 加算配列の累積和
    if i < N {
        addList[i+1] += addList[i]
    }
}

Paizaの練習問題の入力例1をExcelで図解してみる。

  • IMOSを使わない場合
    図で表すと一見シンプル。
    ただし実装は長さ$n$のlistに、区間$l-u$の間だけ$a$を加算する処理を$m$回繰り返すものになる。
    これでは2重ループにどうしてもなってしまうので計算量が$O(n^2)$と多い。
    Imos02.png

  • IMOSを使う場合
    上記コードの「特定区間に加算する値を記録」を図解するとこんな感じ
    Imos03.png

始点～終点だけしか入れていなかった部分を加算していく( addList[i+1] += addList[i]の部分)
imos04.png

計算結果は同一となる。

いもす法
解説を読んでもよく分からなかった人のための「いもす法」の解説

3. アルゴリズム 動的計画法(DP)

最初再帰的にやればいけるだろ！！！って思いこんでやってみたらタイムアウトで普通にダメだった時の解決アルゴリズム。
再帰でツリーの全探索をやろうとして計算量が$O(n^2)$になって絶対これちげえなとなり調べていきついたのがDP。

1つの問題をいくつかの部分問題に分解し、部分問題の解を何度も再利用して問題の解を求める手法。らしい。

再帰的に解を求めつつ、部分問題の解を確保し、次の実行で再利用することで、計算量を抑えられる。

ありふれた例だがフィボナッチ数列の回答。
このアルゴリズムを知るまで私はfibonati(n-1)+fibonati(n-2)みたいな再帰で行けるやろって思いながら実装していたので計算量がバカみたいなことになっていた。

main.go
func main() {
	fmt.Println(fibonati(10)) // 55
	fmt.Println(fibonati(20)) // 6765
}

func fibonati(n int) int {
	fiboMemo := make([]int, n)
	// n < 3は解が1
	fiboMemo[0] = 1
	fiboMemo[1] = 1
	// nまでメモした値を再利用しながら計算する
	for i := 2; i < n; i++ {
		fiboMemo[i] = fiboMemo[i-1] + fiboMemo[i-2]
	}
	return fiboMemo[n-1]
}

動的計画法 DPって何？
うさぎでもわかるアルゴリズム　動的計画法

4. Go BigInt型

int64よりサイズが大きくなる整数を扱う際に利用する型。
いわゆるbigInteger型
累乗式だけはPowではなくExpであることに注意
mathパッケージではPow (power)なのにmath/bigだとExp (Exponent)になるのはちょっと気になるので統一してくれねえかな～～～～

main.go
// 文字列型からBigIntに変換
// 初期化でint64サイズを超える場合はstringから作る
n := new(big.Int)
n, _ = n.SetString(str, 10)

// int64に収まる数値ならbig.NewInt(n)で定義
base := big.NewInt(2)
// 累乗を求める場合はPowではなくExp
beki := base.Exp(base, n, nil)

Goで64bitを超えるの多倍長整数を扱う方法【big.Int解説】

5. アルゴリズム 繰り返し二乗法

定数$N$を$n$乗したい時、$N^n$で計算すると計算量がnの値次第では膨大になってしまう時に使うアルゴリズム
$n$を二進数に変換し、0の時は計算を行わず、1の時だけ計算を行い、それらの累積乗を計算することで、計算量を減らすことができる。

例)$2^5$を求める時

どちらも解は同じなのだが、指数回数の乗算と2進桁数回数の乗算で済むので指数が大きくなる累乗を求める時等は使うことを意識したい。

main.go
// 通常通りに2を5回 指数の回数だけ乗算を行う
ans = 2 * 2 * 2 * 2 * 2

// 繰り返し二乗法の場合
// 指数を2進数変換
bin := strconv.FormatInt(int64(5), 2) // '101'
// 2の階乗を求めるので底Nに2をセット
N := 2
ans, pow := 1, N
// 2進数の桁数分処理を繰り返して求める。
length := len(bin)
for i := 0; i < length; i++ {
    // bit値下1桁を取得
    if bin[len(bin)-1] == '1' {
        ans = ans * pow
    }
    // i乗を求める
    pow = pow * pow
    // 2進数の桁シフト実行
    bin = bin[:len(bin)-1]
}

6. アルゴリズム　素数判定

素数とは

一とその数自身との外には約数がない正の整数。

素数判定を行うにあたり、真っ先に思いつくのは判定したい自然数$n$まで1ずつ加算する$i$で割ってみて判定する方法。
しかしこの方法では計算量$O(n)$であり、自然数
$n$が大きければ大きいほど計算時間が肥大化する。

main.go
for i:=2; i<n; i++ {
    // 割り切れたら終了
    if n%i == 0 { 
        break
    }
}

参考にさせていただいた記事で$\sqrt{n}$まで求めればいいよ。というのがあった。
これは素数の判定というより、自然数$n$が合成数かどうかを判定し、そうでないなら素数と間接的に判断する手法。

合成数とは、1より大きい整数であって、素数でない数です。1とその数自身以外にも約数を持つ数で、4や6などが合成数です。 (GoogleAI引用)

自然数$n$が合成数であるなら、$(a,b)$のペア約数が必ず存在するため、$a×b=n$が成り立つ。
よって以下のどちらかが成り立つ。

a\leq\sqrt{n} \quad \cap \quad b\geq\sqrt{n}

b\leq\sqrt{n} \quad \cap \quad a\geq\sqrt{n}

そのため、$\sqrt{n}$までの自然数で割り切れるかチェックをするだけで済むので計算量が非常に減る。

main.go
var isGouseisu bool
for i := 2; i < int(math.Sqrt(n)); i++ {
    // 合成数判定を得たら終了
    if int(n)%i == 0 {
        isGouseisu = true
        break
    }
}

素数判定アルゴリズムいろいろ

所感

やはりというか今週はレベルアップメニューで出たアルゴリズムの整理がメイン。
全体的に学生時代の学習内容を思い出してくる感じがあった。勉強楽しいねやはり。

この辺りから競プロ入門編になってきた気がする。
AtCoderで水色目指したいので計算量とかその当たりを意識したコーディングを行っていきたい。問題はこの辺りを学んでも業務に活かしにくいところ…
とはいえ知識として計算量をより減らすように考える癖をつけるのは悪いことじゃないのでそこを意識していきたい。

普通に練習問題自体の難易度が高いので進んではいるが未完了。とはいえ着実に進んでいる。
paiza04.png

ちなみにAランクのスキルチェックを先週に引き続き受けたが0点継続。頭の中でロジックを組み立てれはするようになったのだが、計算量が意識できていないのでタイムアウトエラーで負け続けている。悔しい。Month2までにはクリアしてやる。

後これ書いていてQiitaで数式書く方法もわかったのでそれはそれで個人的にプラス。

Qiitaの数式チートシート

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?