【けんちょん本 to Python】-第２章-「問題解決力を鍛える！ アルゴリズムとデータ構造」掲載コードをPythonに書き直してみた！

はじめに

この記事は、競技プログラミングの解説を多数書かれているけんちょんさんの書籍、問題解決力を鍛える！ アルゴリズムとデータ構造（けんちょんさん本）について、掲載コードをPythonに翻訳したものを、備忘のためまとめたものです。

このページでは、第２章掲載分について紹介します！
バグ等ありましたらご容赦ください。

他の章へのリンクは以下のページをご覧ください。
【目次ページ】
https://qiita.com/KevinST/items/002676619a583754bf76

code2.1　一重for文の計算量

一重for文の計算量について示す問題ですね。
出力もつけてみました。

code2-1.py

#Nを入力から受け取り
N = int(input())
count = 0

for i in range(N):
    count += 1

#結果を出力
print(count)

【入力例】
100
【出力例】
100

いわゆる$O(N)$ですね！

code2.2　二重for文の計算量

今度は二重for文の計算量です

code2-2.py

N = int(input())
count = 0
for i in range(N):
    for j in range(N):
        count += 1
print(count)

【入力例】
100
【出力例】
10000

いわゆる計算量$O(N^2$)ですね！

code2.3　偶数の列挙

code2-3.py

N = int(input())
for i in range(N, 1, -2):
    print(i)

【入力例】
10
【出力例】
10
8
6
4
2

計算量は$O(N)$です。

code2.4　最近点対に対する全列挙

code2-4.py

def calc_dist(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5

#入力データを受け取る
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())

#求める値を十分大きい値で初期化しておく
minimum_dist = 10000000.0

#探索開始
for i in range(N):
    for j in range(i+1, N):
        dist_i_j = calc_dist(x[i], y[i], x[j], y[j])
        if dist_i_j < minimum_dist:
            minimum_dist = dist_i_j

print(minimum_dist)

【入力例】
4
1 1
2 2
12 66
18 31
【出力例】
1.4142135623730951

上記の例だと、
- 最近点対は、(1,1) (2,2)
- 距離は$\sqrt2$
- 計算量は$O(N^2)$
です。

第３章はこちら
https://qiita.com/KevinST/items/4d04dc7369880670a63b