異端開発室

再帰を用いた探索手法 再帰は、探索アルゴリズムの実装において非常に強力なツールです。ここでは、いくつかの基本的な列挙問題を再帰関数で解くテンプレートを示します。 部分集合の列挙 (指数型探索) N個の要素からなる集合のすべての部分集合を生成します。各要素について「含める」か「含めない」かの2つの選択肢があるため、計算量はO(2^N)となります。 #include & ...

1. 二分探索木における最小絶対差の取得 二分探索木（BST）の性質として、中序巡回（In-order Traversal）を行うと、ノードの値を昇順で取得できるという特徴があります。この性質を利用することで、隣接するノード間の差分を比較し、最小絶対差を効率的に求めることが可能です。 ポインタ prevNode を使用して、常に現在のノード currNode の直前の値を保持するこ ...

回溯法の基本概念 回溯法（Backtracking）は、探索空間を系統的に調べるアルゴリズム手法です。再帰と密接に関連しており、再帰的な探索過程で「戻る」操作を含むため、この名前が付いています。 この手法の核心は全探索にあります。問題の制約条件を満たすすべての解を列挙し、その中から目的のものを選び出します。効率化のために枝刈り（Pruning）を組み合わせること ...

本記事では、特定のアルゴリズム問題に対するアプローチと実装について考察します。ユニオンファインド、ハッシュテーブル、そして二分木のさまざまな操作（巡回、比較、対称性チェック、パス計算）に焦点を当てます。 アカウントのマージ問題 複数のメールアドレスが同一人物に属するかを判断し、関連するすべてのアドレスを統合する問題について考えます。これは、互い ...

動的計画法を学ぶために、まずは2つの問題から始めましょう。 鋼板の切断問題 1.1 問題の提示 ある企業は長さがnの鋼板をいくつかの断片に切り分けて販売したいと考えています。市場では、長さi（0[r_n = \max_{1\leq i\leq n}( p_i + r_{n-i}) ]よって、この問題を解決するには「トップダウン」の再帰的な方法が利用できます。 1.3 トップダウン再帰実装 public static ...

空間計算量 一般的な再帰は深さ優先探索であり、深さ優先探索の空間計算量は再帰の深さによって決まります。ある方向での再帰が終了すると、その時点で使用していたスタック領域が解放され、同じメモリが再利用されます。 順序リスト 静的順序リスト typedef int SLDataType; #define N 10 struct SeqList { SLDataType a[N]; int size; }; 動的順序リスト seq ...

1. ビールと飲料の購入 解法: 全探索（ブルートフォース） ビール（1缶2.3元）と飲料（1缶1.9元）の合計金額が82.3元。ビールの本数が飲料より少ない条件で計算します。浮動小数点計算の誤差を避けるため、10倍して整数で処理します。 #include <iostream> using namespace std; int main() { for (int beer = 0; beer <= 823 / 23; ++beer) { for ( ...

基本入出力と制御構造 初期学習段階では、標準入出力と基本的な制御フローをマスターすることが重要です。 #include <stdio.h> int main() { // 飛行機のASCIIアート printf(" ** \n"); printf(" ** \n"); printf("************\n"); printf("************\n"); printf(" * * \n"); printf(" * * \n"); ...

1. 点数評価システム #include <stdio.h> char calculateGrade(int score); int main() { int score; char result; while (printf("点数を入力してください: "), scanf("%d", &score) != EOF) { result = calculateGrade(score); printf("Score: %d, Grade: %c\n\n", score, result); } return 0; } char calculateGrade( ...

リスト理論の基礎 リストノードの定義 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next 203. リストから要素を削除する class Solution: def removeElements(self, head, val): dummy_head = ListNode(next=head) current = dummy_head while current.next is not None: ...