Python アルゴリズム編
Pythonで使用するアルゴリズムについて解説します。
目次
- グラフ（Graph）
- ツリー（Tree）
- リスト（List）
- キュー（Queue）
- スタック（Stack）
- ソートアルゴリズム（Sorting Algorithms）
- トライ（Trie）
- 動的計画法（Dynamic Programming）
- バックトラッキング（Backtracking）
- アルゴリズム設計技法（Algorithm Design Techniques）
1. グラフ（Graph）
グラフは、ノード（頂点）とそれらを結ぶエッジ（辺）からなるデータ構造です。
Graph.py
# 隣接リストによるグラフの表現
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(graph)
2. ツリー（Tree）
ツリーは、ルートから始まり、子ノードに分岐する階層構造を持つデータ構造です。
Tree.py
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print(root.value) # Output: 1
print(root.left.value) # Output: 2
print(root.right.value) # Output: 3
3. リスト（List）
リストは、先に説明した通り、順序付きのコレクションです。
List.py
numbers = [1, 2, 3, 4, 5]
print(numbers) # Output: [1, 2, 3, 4, 5]
4. キュー（Queue）
キューは、FIFO（先入れ先出し）データ構造です。queue モジュールを使用します。
Queue.py
from queue import Queue
q = Queue()
q.put(1)
q.put(2)
q.put(3)
while not q.empty():
print(q.get())
# Output: 1 2 3
5. スタック（Stack）
スタックは、LIFO（後入れ先出し）データ構造です。LifoQueue を使用します。
Stack.py
from queue import LifoQueue
stack = LifoQueue()
stack.put(1)
stack.put(2)
stack.put(3)
while not stack.empty():
print(stack.get())
# Output: 3 2 1
6. ソートアルゴリズム（Sort）
ソートアルゴリズムは、データを特定の順序に並べ替えるアルゴリズムです。
Sort.py
# バブルソートの例
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers) # Output: [11, 12, 22, 25, 34, 64, 90]
7. トライ（Trie）
トライは、文字列検索に特化したツリー状のデータ構造です。
Trie.py
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
trie = Trie()
trie.insert("hello")
print(trie.search("hello")) # Output: True
print(trie.search("hell")) # Output: False
8. 動的計画法（Dynamic Programming）
動的計画法は、部分問題の解を再利用して効率的に問題を解くアルゴリズム設計手法です。
Dynamic Programming.py
# フィボナッチ数列の例
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
print(fibonacci(10)) # Output: 55
9. バックトラッキング（Backtracking）
動的計画法は、部分問題の解を再利用して効率的に問題を解くアルゴリズム設計手法です。
Backtracking.py
# ナップサック問題の例
def knapsack(W, weights, values, n):
if n == 0 or W == 0:
return 0
if weights[n-1] > W:
return knapsack(W, weights, values, n-1)
else:
return max(values[n-1] + knapsack(W-weights[n-1], weights, values, n-1),
knapsack(W, weights, values, n-1))
values = [60, 100, 120]
weights = [10, 20, 30]
W = 50
n = len(values)
print(knapsack(W, weights, values, n)) # Output: 220
アルゴリズム設計技法（Algorithm Design Techniques）
アルゴリズム設計技法は、問題を効率的に解決するための方法論です。例として、分割統治法（Divide and Conquer）を紹介します。
Algorithm Design Techniques.py
# マージソートの例
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
L = arr[:mid]
R = arr[mid:]
merge_sort(L)
merge_sort(R)
i = j = k = 0
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr
numbers = [12, 11, 13, 5, 6, 7]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers) # Output: [5, 6, 7, 11, 12, 13]
最後までお読みいただきありがとうございました。