⚔️
アルゴリズム学習はまるでRPGだった話 〜データ構造は武器だ〜
🧠 はじめに
Google 面接のコーディング練習をしているとき、ふと気づいた。
「これ、まるで RPG じゃないか？」
アルゴリズムの世界では、問題が敵で、データ構造が武器だ。
そして、強い武器ほど正しく使わなければ勝てない。
🎮 ステージ 1：まずは“武器の一覧”を覚える
アルゴリズムの敵（問題）はいろいろ出てくるけど、
実は出てくる武器はだいたい同じ。
| 敵（問題タイプ） | よく使う武器（データ構造） |
|---|---|
| 頻繁な探索・存在判定 |
set, dict
|
| 順序を保ちたい |
list, deque, linked list
|
| 最小・最大をすぐ取りたい | heapq |
| 連続区間を扱う | スライディングウィンドウ, bisect
|
| 出現回数のカウント |
Counter, defaultdict
|
| 経路探索 |
deque（BFS）, 再帰（DFS） |
| グルーピングや連結性 | Union-Find |
| 部分一致・文字探索 |
Trie, hash, sliding window
|
⚙️ ステージ 2：考える順番＝戦略の立て方
1️⃣ 問題を理解する
→ 何を求められているか？ どんな制約があるか？
2️⃣ ロジックを考える
→ どうすれば人間が紙で解けるか？
3️⃣ データ構造を選ぶ
→ そのロジックを最速で実現できる構造は何か？
この順番を守るだけで、どんな問題でも落ち着いて対処できる。
🗺 ステージ 3：武器図鑑（データ構造 × O 記法 × コード）
| 構造 | 主な用途 | 操作 | 計算量 | コード例 |
|---|---|---|---|---|
| list | 配列、順序データ |
append, pop, insert
|
末尾 O(1)、中間 O(n) | a.append(1); a.pop() |
| deque | 両端操作 |
appendleft, popleft
|
O(1) | dq = deque(); dq.append(1) |
| set | 重複排除、存在判定 |
in, add, remove
|
平均 O(1) | if x in s: |
| dict | キー → 値マップ |
m[k], get, setdefault
|
平均 O(1) | m = {"a": 1} |
| heapq | 優先度付き最小値 |
heappush, heappop
|
O(log n) | heapq.heappush(h, x) |
| Counter | 頻度集計 |
most_common, update
|
O(n) | cnt = Counter(nums) |
| bisect | ソート＋二分探索 |
insort, bisect_left
|
O(log n)探索、挿入 O(n) | bisect.insort(a, x) |
| linked list | 順序制御・LRU |
_add, _remove
|
O(1)（双方向） | node.prev.next = node.next |
| Union-Find | グループ連結 |
find, union
|
ほぼ O(1) | dsu.union(a,b) |
| Trie | 前方一致探索 |
insert, search
|
O(L)（文字列長） | node = node.child[ch] |
💡 ステージ 4：実際の戦い（例：LRU Cache）
🧩 問題：
最近使われた順で要素を管理し、古いものを自動で削除するキャッシュを設計せよ。
🎯 ゴール：
-
get(key)/put(key, value)を平均 O(1) で実装する。
⚙️ 戦略の立て方
- 「値の取得」は
dictで O(1) - 「順序（古い／新しい）」の管理は
双方向リスト - この 2 つを組み合わせれば理想的！
✅ コード例（Python）
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {}
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._remove(node)
self._add_front(node)
return node.val
def put(self, key: int, val: int) -> None:
if key in self.map:
self._remove(self.map[key])
node = Node(key, val)
self.map[key] = node
self._add_front(node)
if len(self.map) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]
🧩 考察と計算量
| 操作 | 計算量 | 理由 |
|---|---|---|
get |
O(1) | dict で即参照＋リスト移動も O(1) |
put |
O(1) | 追加・削除・更新すべて O(1) |
| 空間 | O(n) | 要素数＋ノード構造分 |
🧭 ステージ 5：解けない時の“思考リセット”
問題がうまく解けないときは、焦らず立ち返る。
次の 3 つを順に整理すると、霧が晴れます。
① 何をやるべきか？
ゴールを一文で言い切る。
- 「○○ を最小化する」
- 「○○ をカウントする」
- 「○○ の順序を保つ」
🧩 → 言葉で整理できない問題は、まだ理解できていない。
② どんな制約があるか？
N, Q, 時間制限、更新有無を読み取る。
- N = 10⁵ → O(n²)は NG
- 「常に更新される」→ ソート済構造は使えない
- 「連続区間」→ スライディングウィンドウ
- 「順序＋削除」→ 双方向リスト
🧩 → 制約を読めば、使える武器が見えてくる。
③ どのデータ構造を使うべきか？
高速にしたい操作を明確に。
| 操作したいこと | 構造 | 計算量 |
|---|---|---|
| 探したい | dict, set | O(1) |
| 両端から出し入れ | deque | O(1) |
| 最小/最大を取りたい | heapq | O(log n) |
| 頻度を数えたい | Counter | O(n) |
| 中間削除 | linked list | O(1) |
| つながり判定 | Union-Find | ほぼ O(1) |
🧩 → 操作単位で考えるのがコツ。
🏁 まとめ：アルゴリズムは攻略ゲーム
- 問題＝敵
- データ構造＝武器
- アルゴリズム＝戦略
- コード＝実戦
どんな問題も、正しい武器を選べば必ず倒せる。
そして、立ち返る場所を持っている人は、どんなバトルにも強い。
今日も一問ずつ、冒険を続けよう ⚔️
Discussion