DSA学習ノート
データ構造とアルゴリズム学習ノート 📝
プログラミングでつまずいたところ、理解できた瞬間、「あ、そういうことか！」と思ったことをまとめています。
学習リスト
基本から始めた部分
配列 (Arrays)
- ポインタで混乱した経験
- 図を描いたら理解できた
- どういう時に配列より便利か
- 最初は本当に理解できなかった
- スタックオーバーフローを経験して学んだこと
- 再帰を使うとエレガントに書ける問題
ソートと探索（よく面接で聞かれる）
- バブルソートから始めて、なぜ遅いか理解した
- クイックソートの分割統治が美しいと思った瞬間
- 実務でどのソートを使うべきか
- off-by-oneエラーとの戦い
- while (left <= right) vs while (left < right) の違い
- 実際に使える場面が意外と多い
ちょっと難しくなってきた部分
- 再帰との相性の良さに気づいた
- バランス木の必要性を実感した話
- 実装は大変だけど理解すると楽しい
- 配列で木を表現できることに驚いた
- 優先度付きキューの便利さ
- ヒープソートの仕組み
- O(1)の魔法
- 衝突処理で悩んだ話
- 良いハッシュ関数とは何か
頭を使う系のアルゴリズム
- 全探索との違いがわからなかった
- 枝刈りの重要性
- パズルを解くのが楽しくなった
- 現実世界の問題に一番近い
- DFSとBFSの使い分け
- ダイクストラ法を理解した時の感動
- 最初は本当に難しかった
- 部分問題への分解がキーだと気づいた
- メモ化から始めるとわかりやすい
- 黒魔術だと思ってた
- XORの便利さに気づいた
- 高速化できるとかっこいい
私の学習方法メモ
- 失敗から学ぶ: バグを出すたびに理解が深まった
- 絵を描く: 特にポインタやグラフは視覚化が大事
- 実装してみる: 読むだけじゃなくて、手を動かすと理解度が違う
- なぜそうなるか考える: 時間計算量の理由を考えると面白い
このノートは学習しながら更新していきます
配列 (Arrays)
2025-08-17
配列についての学習ノート
配列って最初は「ただの箱の並び」だと思ってたけど、実はめちゃくちゃ重要な概念だった。
📚 配列の詳細ページ
配列について深く学ぶために、以下のページに分けてまとめました：
- なぜ配列が高速なのか、メモリレベルで理解する
- 連続メモリの重要性
- アドレス計算の仕組み
- サイズ固定の配列の実装
- 基本操作（挿入、削除、アクセス）
- 時間計算量の詳細
- 自動リサイズの仕組み
- 償却時間計算量の理解
- PythonやJavaScriptの配列の裏側
- LIFO構造の活用
- 括弧チェック、Undo機能の実装
- 関数呼び出しスタックの理解
最初に躓いたこと
インデックスは0から始まる
const arr = [10, 20, 30]; // arr[0] = 10 ← 最初これが違和感あった // arr[1] = 20 // arr[2] = 30 // arr[3] = undefined ← よくやったミス最初の頃、配列の長さが5なのに arr[5] にアクセスしようとしてundefinedが返ってきて「？？？」ってなった。
配列の基本操作で学んだこと
要素の追加・削除
// 末尾に追加 - O(1) 速い！ arr.push(40); // 先頭に追加 - O(n) 遅い... arr.unshift(5); // 全要素を右にずらす必要がある // なるほど、だから配列の先頭操作は避けるべきなのか実際にやってしまった失敗
// ダメな例：配列を走査しながら要素を削除 const nums = [1, 2, 3, 4, 5]; for (let i = 0; i < nums.length; i++) { if (nums[i] % 2 === 0) { nums.splice(i, 1); // インデックスがずれる！ } } // 結果：[1, 3, 5] にならず、[1, 3, 4, 5] になる // 良い例：後ろから走査 for (let i = nums.length - 1; i >= 0; i--) { if (nums[i] % 2 === 0) { nums.splice(i, 1); } }二次元配列で混乱した話
// 最初はこう書いてた（間違い） const matrix = new Array(3).fill(new Array(3).fill(0)); matrix[0][0] = 1; console.log(matrix[1][0]); // 1 !? なんで？ // 理由：同じ配列の参照をコピーしてた // 正しい方法 const matrix = Array.from({length: 3}, () => new Array(3).fill(0));配列のメモリについて理解したこと
配列がなぜ高速なのか：
配列とRAM - メモリの仕組み
2025-08-17
配列がメモリ（RAM）にどう保存されるか学んだこと
最初は「配列って変数をまとめただけでしょ？」と思ってたけど、実際のメモリの仕組みを知ると、なぜ配列が高速なのか理解できた。
そもそもデータ構造って何？
データ構造は、コンピュータのRAM（Random Access Memory）にデータを効率的に保存する方法のこと。RAMは単に「メモリ」とも呼ばれる。
今使ってるパソコンには多分8GB（10⁹バイト）くらいのRAMがある。1バイトは8ビットでできてる。
配列がメモリに保存される仕組み
例えば
[1, 3, 5]という配列があるとする。でもコンピュータは0と1（ビット）しか理解できない。# 整数の配列 arr = [1, 3, 5] # 各数値のバイナリ表現（1バイトで表すと） # 1 = 00000001 # 3 = 00000011 # 5 = 00000101メモリアドレスの仕組みを理解した瞬間
整数は通常4バイト（32ビット）を使う。配列を保存すると：
メモリアドレス | 値 0x1000 | 1 (4バイト) 0x1004 | 3 (4バイト) 0x1008 | 5 (4バイト)重要な発見：アドレスが4バイトずつ離れてる！これが「連続的」ってことか。
文字配列の場合
# 文字の配列 chars = ['A', 'B', 'C'] # 文字は1バイト（8ビット） # メモリでは： # 0x2000: 'A' (1バイト) # 0x2001: 'B' (1バイト) # 0x2002: 'C' (1バイト)文字は1バイトだから、アドレスは1バイトずつ増える。
静的配列 (Static Arrays)
2025-08-17
静的配列の学習ノート
JavaやC++を勉強してて初めて知った「静的配列」。最初はPythonに慣れてたから「なんで最初にサイズ決めなきゃいけないの？」って思った。
静的配列とは
静的型付け言語（Java、C++、C#など）では、配列を作る時にサイズと型を決める必要がある。一度決めたら変更できない。
# Pythonで静的配列をシミュレート class StaticArray: def __init__(self, capacity): self.data = [0] * capacity # 固定サイズ self.capacity = capacity self.length = 0 # 実際に使ってる要素数基本操作と時間計算量
1. 読み込み（アクセス） - O(1)
def get(self, index): if 0 <= index < self.length: return self.data[index] raise IndexError("インデックスが範囲外") # 使用例 myArray = StaticArray(5) myArray.data = [1, 3, 5, 0, 0] # 最初の3つだけ使用 myArray.length = 3 print(myArray.get(1)) # 3を返す（一瞬でアクセス！）なぜO(1)なのか理解した瞬間：
- メモリアドレスが
先頭 + (index × 要素サイズ)で計算できる - 配列のサイズが100でも100万でも、アクセス時間は同じ！
2. 配列の走査 - O(n)
def traverse(self): for i in range(self.length): print(self.data[i]) # または i = 0 while i < self.length: print(self.data[i]) i += 1重要な発見：配列の最後の要素は常に
n-1番目（nは配列サイズ）- メモリアドレスが
動的配列 (Dynamic Arrays)
2025-08-17
動的配列の学習ノート
PythonとJavaScriptのリストって実は「動的配列」だったんだ！サイズが自動で増えるのを「当たり前」と思ってたけど、裏側の仕組みを知って感動した。
動的配列とは
静的配列と違って、要素を追加していくと自動でサイズが増える配列。JavaScriptとPythonではこれがデフォルト。
# Pythonのリストは動的配列 arr = [] # サイズ指定不要！ arr.append(1) arr.append(2) arr.append(3) # 勝手に増えるでも魔法じゃない。実は裏でリサイズという処理が動いてる。
動的配列の実装
class DynamicArray: def __init__(self): self.capacity = 1 # 初期容量 self.length = 0 # 実際の要素数 self.data = [None] * self.capacity def __len__(self): return self.length def __getitem__(self, index): if 0 <= index < self.length: return self.data[index] raise IndexError("Index out of range")末尾への挿入（pushback） - O(1) amortized
def append(self, value): # 容量が足りない場合はリサイズ if self.length == self.capacity: self._resize() # 末尾に挿入 self.data[self.length] = value self.length += 1 def _resize(self): # 容量を2倍にする（これが重要！） self.capacity = 2 * self.capacity new_data = [None] * self.capacity # 既存のデータをコピー for i in range(self.length): new_data[i] = self.data[i] self.data = new_dataなぜ容量を2倍にするのか？
最初これがわからなかった。1.5倍とか、+10とかじゃダメなの？
スタック (Stacks)
2025-08-17
スタックの学習ノート
スタックって「配列の機能制限版」だと最初は思ってた。でも、制限があるからこそ便利な場面があることを知って目から鱗だった。
スタックとは
LIFO（Last In First Out） - 最後に入れたものが最初に出てくる。皿の積み重ねをイメージすると分かりやすい。
↓ push(4) [4] ← top（一番上） [3] [2] [1] ← bottom（一番下） ↑ pop()すると4が出てくるなぜスタックが必要？
最初「配列でよくない？」と思ったけど：
- 意図が明確になる：「LIFO で使う」ことが保証される
- 間違いを防げる：真ん中にアクセスできないから、バグりにくい
- 特定の問題に最適：括弧の対応、関数呼び出し、Undo機能など
基本操作
Push - 要素を追加 O(1)
class Stack: def __init__(self): self.items = [] # 内部は動的配列 def push(self, item): """スタックの頂上に要素を追加""" self.items.append(item) # O(1) amortizedPop - 要素を取り出す O(1)
def pop(self): """スタックの頂上から要素を取り出す""" if not self.is_empty(): return self.items.pop() # O(1) raise IndexError("Pop from empty stack") def is_empty(self): """スタックが空かチェック""" return len(self.items) == 0Peek/Top - 要素を見るだけ O(1)
def peek(self): """頂上の要素を見る（取り出さない）""" if not self.is_empty(): return self.items[-1] # O(1) raise IndexError("Peek from empty stack")完全なスタック実装
class Stack: def __init__(self): self.items = [] def push(self, item): """要素を追加""" self.items.append(item) def pop(self): """要素を取り出す""" if self.is_empty(): raise IndexError("Pop from empty stack") return self.items.pop() def peek(self): """頂上を見る""" if self.is_empty(): raise IndexError("Peek from empty stack") return self.items[-1] def is_empty(self): """空かチェック""" return len(self.items) == 0 def size(self): """サイズを返す""" return len(self.items) def __str__(self): return str(self.items) # 使用例 stack = Stack() stack.push(1) stack.push(2) stack.push(3) print(stack.peek()) # 3 print(stack.pop()) # 3 print(stack) # [1, 2]スタックの実践的な使い方
1. 文字列を逆順にする
def reverse_string(s): stack = Stack() # 全文字をプッシュ for char in s: stack.push(char) # ポップして逆順を作る reversed_str = "" while not stack.is_empty(): reversed_str += stack.pop() return reversed_str print(reverse_string("hello")) # "olleh"2. 括弧の対応チェック（超重要！）
def is_valid_parentheses(s): stack = Stack() pairs = {')': '(', '}': '{', ']': '['} for char in s: if char in '({[': stack.push(char) elif char in ')}]': if stack.is_empty(): return False if stack.pop() != pairs[char]: return False return stack.is_empty() # テスト print(is_valid_parentheses("()[]{}")) # True print(is_valid_parentheses("([)]")) # False print(is_valid_parentheses("{[()]}")) # True3. 式の評価（逆ポーランド記法）
def eval_rpn(tokens): """ 逆ポーランド記法を評価 例: ["2", "1", "+", "3", "*"] → (2+1)*3 = 9 """ stack = Stack() operators = {'+', '-', '*', '/'} for token in tokens: if token in operators: b = stack.pop() a = stack.pop() if token == '+': stack.push(a + b) elif token == '-': stack.push(a - b) elif token == '*': stack.push(a * b) elif token == '/': stack.push(int(a / b)) # 整数除算 else: stack.push(int(token)) return stack.pop() print(eval_rpn(["2", "1", "+", "3", "*"])) # 94. 関数呼び出しスタック（コールスタック）
def factorial(n): """ 再帰関数の裏側でスタックが使われてる """ if n <= 1: return 1 return n * factorial(n - 1) # 実行時のスタックの様子： # factorial(4) # → factorial(3) # → factorial(2) # → factorial(1) # ← 1 # ← 2 * 1 = 2 # ← 3 * 2 = 6 # ← 4 * 6 = 245. Undo機能の実装
class TextEditor: def __init__(self): self.text = "" self.history = Stack() def write(self, text): self.history.push(self.text) # 現在の状態を保存 self.text += text def undo(self): if not self.history.is_empty(): self.text = self.history.pop() def get_text(self): return self.text # 使用例 editor = TextEditor() editor.write("Hello") editor.write(" World") print(editor.get_text()) # "Hello World" editor.undo() print(editor.get_text()) # "Hello"よくある面接問題
Min Stack（最小値を O(1) で取得）
class MinStack: def __init__(self): self.stack = [] self.min_stack = [] # 最小値を記録するスタック def push(self, x): self.stack.append(x) # 最小値スタックを更新 if not self.min_stack or x <= self.min_stack[-1]: self.min_stack.append(x) def pop(self): if self.stack: x = self.stack.pop() if x == self.min_stack[-1]: self.min_stack.pop() return x def top(self): if self.stack: return self.stack[-1] def get_min(self): if self.min_stack: return self.min_stack[-1] # テスト min_stack = MinStack() min_stack.push(3) min_stack.push(5) min_stack.push(2) min_stack.push(1) print(min_stack.get_min()) # 1 min_stack.pop() print(min_stack.get_min()) # 2時間計算量まとめ
操作 時間計算量 備考 Push O(1) 末尾に追加 Pop O(1)* 空チェック必要 Peek/Top O(1)* 空チェック必要 *空のスタックに対する操作はエラー
二分探索 (Binary Search)
2025-08-17
二分探索の学習ノート
「半分ずつ探せばいいじゃん」って簡単に思ってたけど、実装でめちゃくちゃバグを出した。
最初に書いた間違いだらけのコード
// 初心者の頃の間違い function binarySearch(arr, target) { let left = 0; let right = arr.length; // ← arr.length - 1 じゃないとダメ while (left < right) { // ← left <= right が正しい const mid = (left + right) / 2; // ← Math.floor忘れた if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { left = mid; // ← mid + 1 じゃないと無限ループ } else { right = mid; // ← mid - 1 にすべき } } return -1; }正しい実装（やっと理解した）
function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; // 最後のインデックス while (left <= right) { // イコールが重要！ const mid = Math.floor((left + right) / 2); if (arr[mid] === target) { return mid; } else if (arr[mid] < target) { left = mid + 1; // midは違うから+1 } else { right = mid - 1; // midは違うから-1 } } return -1; }なぜ left <= right なのか
これ、めっちゃ悩んだ。図を描いてやっと理解した：
連結リスト (Linked Lists)
2025-08-17
連結リストの学習ノート
このページは作成中です。
ポインタで混乱した経験や、図を描いて理解できた瞬間についてまとめる予定。
予定している内容
- 単方向リスト
- 双方向リスト
- 循環リスト
- 配列との比較
- よくある実装ミス
再帰 (Recursion)
2025-08-17
再帰の学習ノート
このページは作成中です。
最初は本当に理解できなかった再帰。スタックオーバーフローを経験して学んだことをまとめる予定。
予定している内容
- 再帰の基本パターン
- ベースケースの重要性
- 末尾再帰最適化
- メモ化
- 再帰 vs ループ
ソート (Sorting)
2025-08-17
ソートアルゴリズムの学習ノート
このページは作成中です。
バブルソートから始めて、なぜ遅いか理解した経験をまとめる予定。
予定している内容
- バブルソート、選択ソート、挿入ソート（O(n²)）
- マージソート、クイックソート（O(n log n)）
- ヒープソート
- 基数ソート、カウンティングソート
- 実務での使い分け
木構造 (Trees)
2025-08-17
木構造の学習ノート
このページは作成中です。
再帰との相性の良さに気づいた瞬間についてまとめる予定。
予定している内容
- 二分木の基本
- 二分探索木（BST）
- 木の走査（前順、中順、後順）
- バランス木（AVL木、赤黒木）
- 実装のコツ
ヒープ (Heap)
2025-08-17
ヒープの学習ノート
このページは作成中です。
配列で木を表現できることに驚いた経験をまとめる予定。
予定している内容
- 最大ヒープ・最小ヒープ
- ヒープの性質
- 優先度付きキューの実装
- ヒープソート
- 実用例
ハッシュ (Hashing)
2025-08-17
ハッシュの学習ノート
このページは作成中です。
O(1)の魔法について理解した瞬間をまとめる予定。
予定している内容
- ハッシュ関数の仕組み
- ハッシュテーブルの実装
- 衝突処理（チェイン法、オープンアドレス法）
- 良いハッシュ関数の設計
- 実用例
バックトラッキング (Backtracking)
2025-08-17
バックトラッキングの学習ノート
このページは作成中です。
全探索との違いがわからなかった経験をまとめる予定。
予定している内容
- バックトラッキングの基本
- 枝刈りの重要性
- N-Queens問題
- 数独ソルバー
- 組み合わせ生成
グラフ (Graphs)
2025-08-17
グラフの学習ノート
このページは作成中です。
現実世界の問題に一番近いデータ構造についてまとめる予定。
予定している内容
- グラフの表現（隣接リスト、隣接行列）
- DFS（深さ優先探索）
- BFS（幅優先探索）
- 最短経路アルゴリズム（ダイクストラ、ベルマンフォード）
- 実用例
動的計画法 (Dynamic Programming)
2025-08-17
動的計画法の学習ノート
このページは作成中です。
最初は本当に難しかった動的計画法。部分問題への分解がキーだと気づいた瞬間をまとめる予定。
予定している内容
- DPの基本的な考え方
- トップダウン（メモ化）
- ボトムアップ
- 典型的なDP問題
- 状態遷移の設計
ビット操作 (Bit Manipulation)
2025-08-17
ビット操作の学習ノート
このページは作成中です。
黒魔術だと思ってたビット操作。XORの便利さに気づいた瞬間をまとめる予定。
予定している内容
- ビット演算の基本
- AND、OR、XOR、NOT
- ビットシフト
- ビットマスク
- 高速化テクニック