『アルゴリズムのキホン』を読みました & AOJでやってみた! 【書評】


数年前に読んだ『アルゴリズムのキホン』を再勉強も兼ねて読みなおしています。プログラミングの基礎力を高めるのが今の目標なので徹底的に頑張ります!

ちなみに、アルゴリズム系を勉強するときにオススメなのが、会津大学が提供している『Aizu Online Judge』です。
日本語の問題も多数ありますし、何よりほかの人の回答があるので、効率的なコードを参考にできるのがよいです。
また、新しい言語を勉強するときにも、パズルをとくような感覚で勉強していけるのですごくいい練習になると思います!


データ構造

🐯 ハッシュテーブル

データを入力値としたハッシュ関数により得られる値が、ルート配列の要素番号となる

データ構造

1) ルート配列と呼ばれる要素数Nの配列
2) ルート配列の要素を先頭ポインタとするリスト => ルート配列の各要素がデータを管理

アルゴリズム

🎳 計算量

  • アルゴリズムの効率性は、「時間計算量」と「領域計算量」に着目する
  • 時間計算量 =「演算」「条件比較」などの処理の操作回数で表す
  • 領域計算量 = 使用するメモリ領域の大きさを表す

algorithm-calc-cost

  • O(1) => Nに依存しない計算量
  • O(n) => 計算量がNに比例する
  • O(n**2) => NxN会の操作がひつような計算。バブルソートなど
  • O(log2n) => 二分木探索(バイナリサーチ)のような1回操作するたびに1/2に狭まる計算量

calculation-cost

🍣 ソートアルゴリズムの種類

選択ソート

  • データの中から最小値(最大値)を見つけ出して、先頭(末尾)のデータと交換を行う

バブルソート

  • 隣り合うデータどうしを比較して、大小関係が正しくなるように並び替える

マージソート

  • ソート対象データ列を分割していき、再度マージすることで並び替える

クイックソート

  • データ列から任意の数を選び、その値との大小で2分割することを繰り返して並び替える

😎 ユークリッドの互除法

概要

ユークリッドの互除法 - Wikipedia

Rubyで最小公倍数を求める

サンプル問題(AOJ)

GCD and LCM - Aizu Online Judge

Aizu Online Judgeの最大公約数(GCM: the greatest common divisor)と、最小公倍数(LCM: least common multiple)を求める問題。

Rubyのサンプルソース

class Array
# 最大公約数: 2つ以上の正の整数に共通な約数(公約数)のうち最大のもの
def lcm
self.inject do |a, b|
a*b/self.gcd
end
end
# 最小公倍数: 2つ以上の正の整数の共通な倍数(公倍数)のうち最小のもの
# ユークリッドの互除法
def gcd
self.inject do |a, b|
while b > 0
a, b = b, a if a < b
a, b = b, a%b
end
return a
end
end
end
while str = gets
a = str.split(' ').map(&:to_i)
puts "#{a.gcd} #{a.lcm}"
end
# output
# 2 24
# 10000000 150000000

Pythonのサンプルソース

# coding:utf-8
import sys
# 最大公約数
def gcd(a, b):
while b > 0:
a, b = b, a%b
return a
# 最小公倍数
def lcm(a, b):
return a*b/gcd(a, b)
for s in sys.stdin:
a, b = map(int,s.split())
gcd_num = gcd(a, b)
lcm_num = lcm(a, b)
print "%d %d"%(gcd_num, lcm_num)
# output
# 2 24
# 10000000 150000000

🎃 動的計画法

概要

動的計画法を簡単に説明すると、「途中経過をメモしておいて、次の計算で使う」こと。

サンプル問題(AOJ)

A First Grader

Aizu Online Judge。動的計画法を使って数式のパターン数を計算する問題。

Rubyサンプルソース

n = gets.to_i
arr = gets.split(' ').map(&:to_i)
dp = Array.new(n-1) { Array.new(21, 0) }
answer = arr[n-1]
dp[0][arr[0]] = 1
1.upto(n-2) do |i|
0.upto(20) do |j|
next if dp[i-1][j] == 0
add = j + arr[i]
sub = j - arr[i]
dp[i][add] += dp[i-1][j] if add <= 20
dp[i][sub] += dp[i-1][j] if sub >= 0
end
end
puts dp[n-2][answer]

Pythonサンプルソース

n = input()
arr = map(int, raw_input().split())
answer = arr[n-1]
dp = [[0]*21 for i in range(n)]
dp[0][arr[0]] = 1
for i in range(1, n-1):
for j in range(21):
if dp[i-1][j] == 0: continue
vp = j + arr[i]
vm = j - arr[i]
if vp <= 20:
dp[i][vp] += dp[i-1][j]
if vm >= 0:
dp[i][vm] += dp[i-1][j]
print dp[n-2][answer]

🗻 ポーカーの手札から役を求める

サンプル問題

Poker Hand

ポーカーの手札から役を答える問題。そんなに難しくない問題なので頭の体操にピッタリ!

Rubyのサンプルソース

while s = gets do
cards = s.split(',').map(&:to_i)
card_count = Array.new(13){0}
cards.each { |c| card_count[c-1] += 1 }
str = card_count.join
card_count.delete(0)
scr = 'null'
case card_count.sort
when [1,4]
scr = 'four card'
when [2,3]
scr = 'full house'
when [1,1,1,1,1]
scr = 'straight' if str =~ /1{5}/ or str =~ /10{8}1{4}/
when [1,1,3]
scr = 'three card'
when [1,2,2]
scr = 'two pair'
when [1,1,1,2]
scr = 'one pair'
end
puts scr
end

Pythonのサンプルソース

import sys
for s in sys.stdin:
hand = sorted(map(int, s.split(',')))
kind = len(set(hand))
ma = max([hand.count(i) for i in hand])
ans = 'null'
if kind == 4:
ans = 'one pair'
elif kind == 3:
if ma == 2:
ans = 'two pair'
else:
ans = 'three card'
elif kind == 2:
if ma==4:
ans = 'four card'
else:
ans = 'full house'
else:
if hand == [1,10,11,12,13] or (hand[4] - hand[0]) == 4:
ans = 'straight'
print ans

🗽 Aizu Online Judgeのサンプルソース

当面はAOJを解きながら、アルゴリズムの再勉強をしていくつもりです。Ruby/PythonでのAOJの回答は下のリポジトリに保存しておきます。もしツッコミとかあればぜひ^^

morizyun/aoj-ruby-python - GitHub

🏀 変更来歴

  • (2014-04-29 14:55) 動的計画法の解法を追加
  • (2014-05-01 20:50) ポーカーの手札の解法を追加
  • (2017-03-12 08:40) 各種調整

🚜 Secial Thanks

📚 おすすめの書籍