医療とテクノロジーの交差点にて【第３話】プログラミング初心者が学ぶべき３つのポイント

どうも、トア・ルドクターです！
今回はプログラミング初心者を対象に、プログラミングの基本的かつ大切な考え方について解説しようと思います。というのも、『小難しい記事を書いても中級者以上の方には需要がなく、しかも下調べ・推敲といった労力を要するのでコスパが悪い。一方で、初心者向けの記事は簡単に書けるわりに、案外ニーズがあって宣伝になりそう』という打算的な目論見があるからです。

それでは、大きく３つのテーマに分けて解説していきます。本記事のコードはすべてpython3を用いております。

（１）困難は分割する

ルネ・デカルトの著書『方法序説』の中に『困難は分割せよ』という有名な言葉がありますね。ことプログラミングにおいても、これはとても大切な考え方になります。どんなに複雑な処理でも、紐解けば、一つ一つの単純な手続きの組み合わせで実装できるわけです。ここではソート・アルゴリズム（数字のみの配列において、数字を昇順or降順に整理すること）を例に見ていきましょう。ソートにも様々な方法があるのですが、今回扱うのは『バブルソート』と呼ばれる方法です。

【問題１】
配列 [8,3,6,2,7,9,1,5] をバブルソートを用いて昇順ソートせよ。
（バブルソートの説明もしてないので解説を読み流せばOK）

まず、基本知識について一通りまとめておきます。

配列

arr = [1,2,3]     # arrはarray「配列」の意味

print(arr[0])     # １つ目の要素のインデックスは0
print(arr[1])     # ２つ目の要素のインデックスは1
print(arr[2])     # 3つ目の要素のインデックスは2
-------------------------------
>>
1
2
3

if-文

num = 3                          # numはnumber「数字」の意味

if num%2 == 0 : print("Even")    # numが偶数の場合  # num%2 は「numを２で割った余り」
else: print("Odd")               # numが奇数の場合
-------------------------------
>> Odd

for-文

arr = [1,2,3]
n = len(arr)            # lenはlength「長さ」の意味で、配列の要素数を求める関数

for i in range(n):      # iという変数を0からn-1まで動かしていく
    print(arr[i])
    if arr[i]%2 == 0 : print("Even")
    else: print("Odd")
---------------------------
>>
1
Odd
2
Even
3
Odd

基本知識は以上です。初学者には若干不親切かも知れませんが、このレベルに関しては『習うより慣れろ』的な部分が大きいです。
それでは『バブルソート』の実装です。

arr = [8,3,6,2,7,9,1,5,4]
n = len(arr)

for i in range(n):
   for j in range(n-1,i, -1):
       if arr[j] < arr[j-1]:
           arr[j], arr[j-1] = arr[j-1], arr[j]    # ２つの文字を入れ替える

print(arr)
----------------------------
>> [1,2,3,4,5,6,7,8,9]

アルゴリズムの解説です。２つ目のforループ（jのループ）で最後尾の要素から i番目の要素まで参照していき『小さいのを前に！』を繰り返すと、『見た中で一番小さいものが一番前にいる』状態が作れます。１回目の操作で一番小さい１が先頭にいく。２回目の操作で、すでに並べた１を除き、一番小さい２が先頭（１の次）にいく。３回目の操作で、すでに並べた１・２を除き、一番小さい３が先頭（２の次）にいく。・・・こんな作業を１つ目のforループ（iのループ）によってN回繰り返すと、全ての要素が小さい順に並べ替えられたことになります。シャンパンの泡が上へ上へとブクブク泡立つように、要素が順々に前へと送られていくことが『バブルソート』という呼称の由来です。実に分かりにくい名称ですね。

さて、今回用いたのは『配列・if-文・for-文』という基本知識のみですが、これらの組み合わせで『バブルソート』という少し高度なプログラムを実装することができました。余談ですが、私が自作した 『NEVER-NOTE』というメモアプリでも、メモのand/or検索機能を『配列・for-文・if-文』のみで実装しています。今後どこかでソースコードも公開する予定です。

（２）発想力が大事

アインシュタインいわく『想像力は知識より大切である』ですが、実際は、プログラミングにおいて最低限の知識は必要です。多分あらゆる分野において言えることでしょう。その上でプログラミングには、限られた知識の中でもアイディア１つで難しい問題を解決しうる可能性と興趣があります。寧ろ、柔軟な発想ができないと解決できない問題も多々あります。具体例として次の問題を考えてみてください。

【問題２】
ある核酸配列（A / T / G / Cからなる文字列）の相補鎖（AとT、GとCを入れ替えた文字列）を出力するプログラムを記述せよ。
例えば、"ATTGCC" の相補鎖は "TAACGG" である。
（正確には "GGCAAT" と更に反転したものだが問題の本質ではない）

なお、文字を入れ替える replaceメソッドは既知として構いません。replaceメソッドの使い方を説明しておきます。

DNA = "ATTGCC"
cDNA = DNA.replace("A","T") # AをTに変更
print(cDNA)

------------------------------------------------------
> TTTGCC

この問題を解くのに必要な知識はこれだけなのですが、正解に至るには一工夫を要します。少し考えれば、次のようなコードは不正解だと気づくでしょう。

DNA = "ATTGCC"
cDNA = DNA.replace("A","T").replace("T","A").replace("G","C").replace("C","G")
print(cDNA)

------------------------------------------------------
> AAAGGG

おわかりでしょうか。replaceメソッドは左から順に処理するため、このコードだと文字列の変化が ATTGCC → TTTGCC → AAAGCC → (以下略) のようになってしまい、題意を満たしません。
正解は以下の通りです。

DNA = "ATTGCC"
DNA = DNA.replace("A","a").replace("T","t").replace("G","g").replace("C","c")
cDNA = DNA.replace("a","T").replace("t","A").replace("g","C").replace("c","G")
print(cDNA)

------------------------------------------------------
> TAACGG

いったん A / T / G / C の文字すべてを小文字に置き換えてから処理することによって上述のピットフォールを回避できるのです。プログラミングをする上でこのような創意工夫は至極大切です。

（３）計算量が大事

ここまで学んだように、単純な手続きの組み合わせで難しい問題も解決できるわけですが、その組み合わせ方次第では、１つの問題に対して多彩なアプローチが考えられます。
しかしながら、どんな方法でもいいわけではなく、同じ作業をするならば実行時間が短い（＝実行速度が早い）方が効率的なプログラムだと言えます。そこには明らかな優劣があり、拘るべきポイントです。
効率的なプログラムを書くためには、計算量（オーダー）という概念が重要になります。簡単な例を出しましょう。

【問題３】
以下の条件式を満たす自然数(a, b, c)の組は幾つあるか？
a + b = c
a <= 100 , b <= 100 , c <= 100

どうやっても解けますが、２通りの解答を示します。

# 解放１
ans = 0
for a in range(1,101):
    for b in range(1,101):
        for c in range(1,101):
            if a + b == c : ans += 1
print(ans)
--------------------------------------
> 4950

# 解法２
ans = 0
for a in range(1,101):
    for b in range(1,101):
        if a + b < 101 : ans += 1
print(ans)
--------------------------------------
> 4950 

これら２つのコードを比べると後者のが圧倒的に効率的です。
前者は100^3（100万）パターンの試行をしているのに対し、後者は100^2（1万）パターンの試行しかしていません。
即ち、後者の方が計算量が1 / 100（計算速度が100倍）というわけです。
一般化した議論をする際には、計算機科学のパイオニアといえるドナルド・クヌースが提唱した漸近記法が有用です。前者は O(N^3) オーダーと表現され、後者は O(N^2) オーダーと表現されます。尚、Oはオミクロンと読みます。

【問題４】
以下の条件式を満たす自然数(a, b, c)の組は幾つあるか？
a^2 + b^2 = c^2
a <= 100 , b <= 100 , c <= 100
（いわゆるピタゴラス数の問題）

先程の問題のいわば応用問題ですね。少し難易度が上がります。
a, b, cすべて100回まわす方法は O(N^3) オーダーですが、これだと効率が悪いので工夫を要します。ここでも『発想力が大事』なわけです。

ans = 0
squares = [i**2 for i in range(1,101)]    # 平方数のリスト
for a in range(1,101):
   for b in range(1,101):
       if a**2 + b**2 in squares: ans += 1
print(ans)
--------------------------------------------
>> 104

先に平方数のリストを作成しておいて、a^2 + b^2 の値が平方数のリストに含まれるかを判定する方法です。これならcを馬鹿正直に全通り回す必要がないので幾分か効率的になります。ここで『平方数のリストを全部照合していくのなら、結局は O(N^3) オーダーみたいなもんじゃん！』という疑問を持つ方がいると思いますが、実は『平方数のリストを照合する』計算量自体は O(N) ではなく O(log N) なのです（これは二分探索(binary-search)というアルゴリズムなのですが調べてみてください）。したがって、このコード全体の計算量を漸近記法で表すと O(N^2 * log N) オーダーになります。

今回扱った４問については自力でコーディングできるように是非とも復習してみてください！
最後にAtCoderから応用問題を１問引用しますので、是非チャレンジしてみてください。
https://atcoder.jp/contests/tenka1-2017-beginner/tasks/tenka1_2017_c

それではまたいつか！

【著者プロフィール】
都内で医師として研鑽する傍ら、独学でプログラミングを学ぶ26歳。趣味は『ギター / バイオリン / 美術鑑賞 / youtube鑑賞 / 創作料理 / 囲碁 / チェス / 折り紙 / スノボ / サーフィン / ドライブ』など枚挙にいとまがない。CIAの格闘武術クラブマガを始める。得意料理はバナナシチュー。ビールと牡蠣は生派だが生セックスは断固せず、経験人数の常用対数は２未満と清純を極める。略歴としては高２で数学全国１位（駿台）、文系で官僚をめざすも、ドラマ『コードブルー』の影響から気づいたら医師に。ディープラーニングG検定、統計検定２級、知的財産検定３級など取得。TOEICは次回900目指す予定（仮）。

【記事アーカイブ】
【第１話】医者なのにプログラミングを勉強してみた話
【第２話】pythonプログラミングの小技（１）ラムダ
【第３話】プログラミング初心者が学ぶべき３つのポイント
【第４話】競技プログラミングのススメ
【第５話】競技プログラミング物語（１）バイトリーダーの苦悩
【第６話】プログラミングで自作する実用アプリ（１）NEVER-NOTE
【第７話】プログラミングで解析したDNA鑑定の精度
【第８話】統計学は最強の学問であるのか？
【第９話】プログラミングすれば人類最高IQに対抗できる説