はじめに
プログラミングのスキルアップにおいて避けて通れないのが「アルゴリズム思考」です。特に業務での問題解決や競技プログラミング、コーディング面接に挑戦する際には、よく出る「実装パターン」を身につけておくことが武器になります。
本記事では、Python中級者向けに「よく出るアルゴリズムの実装パターン10選」を、コード例付きでわかりやすく解説します。
この記事でわかること
- 実務や面接で頻出のアルゴリズム実装パターン
- Pythonでの簡潔な書き方・考え方
- アルゴリズム思考を鍛える練習法
1. スライディングウィンドウ法
用途：部分列の最大値、固定長の範囲での集計に便利。
def max_sum_subarray(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
2. ツーポインター法
用途：ソート済み配列から条件に合うペアや範囲を探す。
def has_pair_with_sum(arr, target):
arr.sort()
left, right = 0, len(arr) - 1
while left < right:
curr_sum = arr[left] + arr[right]
if curr_sum == target:
return True
elif curr_sum < target:
left += 1
else:
right -= 1
return False
3. バイナリサーチ（二分探索）
用途：ソート済みリストから要素を高速に探す。
import bisect
def binary_search(arr, target):
index = bisect.bisect_left(arr, target)
return index < len(arr) and arr[index] == target
4. 累積和（Prefix Sum）
用途：区間の合計値を高速に計算。
def prefix_sum(arr):
prefix = [0]
for num in arr:
prefix.append(prefix[-1] + num)
return prefix
5. DFS（深さ優先探索）
用途：グラフ探索、再帰的処理、バックトラッキングなど。
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
6. BFS（幅優先探索）
用途：最短経路探索、レベル順の探索。
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node in visited:
continue
visited.add(node)
queue.extend(graph[node])
return visited
7. メモ化再帰（Top-Down DP）
用途：フィボナッチ数列、ナップサック問題などで計算量を削減。
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
8. 動的計画法（Bottom-Up DP）
用途：最適解を小さい問題から積み上げて解く。
def climb_stairs(n):
if n <= 2:
return n
dp = [0, 1, 2]
for i in range(3, n + 1):
dp.append(dp[i - 1] + dp[i - 2])
return dp[n]
9. ビット演算を用いた全探索
用途：集合の部分列の全パターンなど、2^N通りの探索に便利。
def all_subsets(arr):
n = len(arr)
for i in range(1 << n):
subset = [arr[j] for j in range(n) if (i >> j) & 1]
print(subset)
10. Union-Find（素集合データ構造）
用途：グループ分け、連結判定に強い。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
self.parent[self.find(x)] = self.find(y)
まとめ：アルゴリズムは「考え方」と「型」で身につく
Pythonでアルゴリズムを学ぶ最大のメリットは、記述がシンプルなので思考に集中できることです。今回紹介した10のパターンは、「考え方の引き出し」としてぜひ何度も手を動かして習得してみてください。
