Python アルゴリズム編

# Python アルゴリズム編
Pythonで使用するアルゴリズムについて解説します。

### 目次
1. グラフ（Graph）
2. ツリー（Tree）
3. リスト（List）
4. キュー（Queue）
5. スタック（Stack）
6. ソートアルゴリズム（Sorting Algorithms）
7. トライ（Trie）
8. 動的計画法（Dynamic Programming）
9. バックトラッキング（Backtracking）
10. アルゴリズム設計技法（Algorithm Design Techniques）

**1. グラフ（Graph）**
グラフは、ノード（頂点）とそれらを結ぶエッジ（辺）からなるデータ構造です。
```python: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）**
ツリーは、ルートから始まり、子ノードに分岐する階層構造を持つデータ構造です。
```python: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）**
リストは、先に説明した通り、順序付きのコレクションです。
```python:List.py
numbers = [1, 2, 3, 4, 5]
print(numbers)  # Output: [1, 2, 3, 4, 5]
```

**4. キュー（Queue）**
キューは、FIFO（先入れ先出し）データ構造です。queue モジュールを使用します。
```python: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 を使用します。
```python: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）**
ソートアルゴリズムは、データを特定の順序に並べ替えるアルゴリズムです。
```python: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）**
トライは、文字列検索に特化したツリー状のデータ構造です。
```python: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）**
動的計画法は、部分問題の解を再利用して効率的に問題を解くアルゴリズム設計手法です。
```python: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）**
動的計画法は、部分問題の解を再利用して効率的に問題を解くアルゴリズム設計手法です。
```python: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）を紹介します。
```python: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]
```

最後までお読みいただきありがとうございました。