【2025年版】アルゴリズムとデータ構造入門完全ガイド – 初心者でもわかる基本から実践まで
アルゴリズムとデータ構造とは？
アルゴリズムは問題を解決するための手順や方法、データ構造はデータを効率的に格納・操作するための仕組みです。プログラミングにおいて最も重要な基礎知識であり、効率的なソフトウェア開発に不可欠な概念です。
学習するメリット
- 問題解決能力の向上：複雑な問題を体系的に解決
- プログラムの効率化：実行時間とメモリ使用量の最適化
- 技術面接対策：多くの企業で重要視される知識
- より良い設計：適切なデータ構造選択で保守性向上
計算量（時間計算量・空間計算量）
Big O記法の基本
# O(1) - 定数時間
def get_first(arr):
return arr[0]
# O(n) - 線形時間
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
# O(n²) - 二次時間
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]
計算量の比較
| 計算量 | 実行時間例（n=1000） | 例 |
|---|---|---|
| O(1) | 1 | 配列の要素アクセス |
| O(log n) | 10 | 二分探索 |
| O(n) | 1,000 | 線形探索 |
| O(n log n) | 10,000 | マージソート |
| O(n²) | 1,000,000 | バブルソート |
基本的なデータ構造
1. 配列（Array）
# 配列の基本操作
numbers = [1, 2, 3, 4, 5]
# アクセス: O(1)
first = numbers[0]
# 検索: O(n)
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
# 挿入: O(n)
numbers.insert(2, 10) # インデックス2に10を挿入
2. 連結リスト（Linked List）
class ListNode:
def __init__(self, val=0):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
new_node = ListNode(val)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
def prepend(self, val): # O(1)
new_node = ListNode(val)
new_node.next = self.head
self.head = new_node
3. スタック（Stack）
class Stack:
def __init__(self):
self.items = []
def push(self, item): # O(1)
self.items.append(item)
def pop(self): # O(1)
if not self.is_empty():
return self.items.pop()
return None
def peek(self): # O(1)
if not self.is_empty():
return self.items[-1]
return None
def is_empty(self):
return len(self.items) == 0
# 括弧の対応チェック
def is_valid_parentheses(s):
stack = Stack()
pairs = {'(': ')', '[': ']', '{': '}'}
for char in s:
if char in pairs:
stack.push(char)
elif char in pairs.values():
if stack.is_empty() or pairs[stack.pop()] != char:
return False
return stack.is_empty()
4. キュー（Queue）
from collections import deque
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item): # O(1)
self.items.append(item)
def dequeue(self): # O(1)
if not self.is_empty():
return self.items.popleft()
return None
def is_empty(self):
return len(self.items) == 0
# 幅優先探索での使用例
def bfs(graph, start):
visited = set()
queue = Queue()
queue.enqueue(start)
visited.add(start)
while not queue.is_empty():
node = queue.dequeue()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue(neighbor)
5. ハッシュテーブル（辞書）
# Python の辞書（ハッシュテーブル）
hash_table = {}
# 挿入・更新: O(1) 平均
hash_table["key1"] = "value1"
# 検索: O(1) 平均
value = hash_table.get("key1")
# 削除: O(1) 平均
del hash_table["key1"]
# 実用例：文字数カウント
def count_chars(text):
char_count = {}
for char in text:
char_count[char] = char_count.get(char, 0) + 1
return char_count
result = count_chars("hello") # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
基本的なアルゴリズム
1. 探索アルゴリズム
線形探索
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
# 時間計算量: O(n)
二分探索
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# 時間計算量: O(log n)
# 前提条件: ソート済み配列
2. ソートアルゴリズム
バブルソート
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
# 時間計算量: O(n²)
マージソート
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 時間計算量: O(n log n)
クイックソート
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 平均時間計算量: O(n log n)
# 最悪時間計算量: O(n²)
木構造とグラフ
1. 二分木
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
# 二分木の走査
def inorder_traversal(root):
if root is None:
return []
result = []
result.extend(inorder_traversal(root.left))
result.append(root.val)
result.extend(inorder_traversal(root.right))
return result
def tree_height(root):
if root is None:
return 0
return 1 + max(tree_height(root.left), tree_height(root.right))
2. 二分探索木（BST）
class BST:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert_recursive(self.root, val)
def _insert_recursive(self, node, val):
if node is None:
return TreeNode(val)
if val < node.val:
node.left = self._insert_recursive(node.left, val)
else:
node.right = self._insert_recursive(node.right, val)
return node
def search(self, val):
return self._search_recursive(self.root, val)
def _search_recursive(self, node, val):
if node is None or node.val == val:
return node
if val < node.val:
return self._search_recursive(node.left, val)
return self._search_recursive(node.right, val)
3. グラフ探索
深さ優先探索（DFS）
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
stack.extend(graph[node])
幅優先探索（BFS）
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
動的プログラミング
1. フィボナッチ数列（メモ化）
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
# Python のデコレータ使用
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_cached(n):
if n <= 1:
return n
return fibonacci_cached(n-1) + fibonacci_cached(n-2)
2. ナップサック問題
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
dp[i][w] = max(
values[i-1] + dp[i-1][w - weights[i-1]],
dp[i-1][w]
)
else:
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
# 使用例
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
max_value = knapsack(weights, values, capacity)
実践的な問題解決例
1. LRU キャッシュ
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key) # 最近使用済みに移動
return self.cache[key]
return -1
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # 最も古いものを削除
2. 最短経路問題（ダイクストラ法）
import heapq
def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
3. 文字列マッチング
def kmp_search(text, pattern):
def build_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = build_lps(pattern)
matches = []
i = j = 0
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
matches.append(i - j)
j = lps[j - 1]
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return matches
パフォーマンス最適化のコツ
1. 適切なデータ構造の選択
# 頻繁な検索 → ハッシュテーブル
user_data = {"user1": "data1", "user2": "data2"}
# 順序付きデータ → 配列
scores = [85, 92, 78, 96]
# LIFO操作 → スタック
undo_stack = []
# FIFO操作 → キュー
from collections import deque
task_queue = deque()
2. アルゴリズムの選択基準
# データサイズが小さい（n < 50）→ 挿入ソート
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# データサイズが大きい → マージソート/ヒープソート
# ランダムデータ → クイックソート
学習ロードマップ
初級レベル（1-2ヶ月）
- 基本データ構造：配列、連結リスト、スタック、キュー
- 基本アルゴリズム：線形探索、バブルソート
- 計算量の概念：Big O記法の理解
- 実装練習：基本的なデータ構造を自作
中級レベル（3-4ヶ月）
- 効率的なアルゴリズム：二分探索、マージソート、クイックソート
- 木構造：二分木、二分探索木、ヒープ
- グラフアルゴリズム：DFS、BFS、最短経路
- ハッシュテーブル：ハッシュ関数、衝突処理
上級レベル（6ヶ月以上）
- 高度なアルゴリズム：動的プログラミング、貪欲法
- 複雑なデータ構造：AVL木、B木、トライ
- グラフの高度な問題：最小全域木、ネットワークフロー
- 文字列アルゴリズム：KMP、ローリングハッシュ
実践問題集
- 初級：配列の回転、括弧の対応チェック
- 中級：二分探索木の実装、最短経路探索
- 上級：LRUキャッシュ、文字列マッチング
まとめ
アルゴリズムとデータ構造は、効率的なプログラムを作成するための基礎知識です。適切なデータ構造を選択し、効率的なアルゴリズムを実装することで、大規模なデータでも高速に動作するソフトウェアが開発できます。
重要なのは、理論だけでなく実際にコードを書いて理解を深めることです。計算量を意識し、問題に応じて最適な手法を選択できるようになることが目標です。継続的な練習を通じて、アルゴリズム思考を身につけていきましょう。
■プロンプトだけでオリジナルアプリを開発・公開してみた！！
■AI時代の第一歩！「AI駆動開発コース」はじめました！
テックジム東京本校で先行開始。
■テックジム東京本校
「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。
＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。
＜月1開催＞放送作家による映像ディレクター養成講座
＜オンライン無料＞ゼロから始めるPython爆速講座
