アルゴリズム
木の中の部分木の数を数える考え方は簡単． ・再帰的に考える ・部分木の数を，①自身のノードを含んでも含まなくてもどちらでも良いケース，②自身のノードを含む必要があるケース，で分けて考える．メモする． ①→部分木の数は，各子供(①)の部分木の数の積 ＋…
・Stackにサイズがあり，サイズを超えてpushしようとすると次のStackにpushされる． ・SetOfStacksクラスからは通常のStackのようにpop()，push()が実行できる．世界で戦うプログラミング力を鍛える150問の中の一つの問題． 答えは，SetOfStacksクラスにArra…
動的計画法◆動的計画法 ◯ポイント 1.ある問題の解は、より小さな問題の解を含んでいる 2.回帰的な解は、少ない数の、小さな問題の繰り返しである 3.テーブルをボトムアップで計算する◯例題(Longest Common subseence:LCS) ・二つの文字列x[1,...,m]とy[1,...…
データ構造2、特殊なリスト◆skip lists ◯特徴 ・複数のsorted linked listを用いた、シンプルで効率的な動的探索データ構造 ・小田急線みたいな感じ。各駅停車リスト、準急リスト、急行リスト、快速急行リストがあって、例えば、各停も準急も止まる駅では乗…
データ構造1、木◆二分探索木 BST(Binary Search Tree) ◯特徴 各ノードに値をもち、 その値が左の子ノードの値以上で、 右の子ノードの値以下であるような2分木 ・詳細はここで→http://www.geocities.jp/h2fujimura/mutter/tree/binary-search-tree.html ・ク…
Hashingnレコードを持つテーブルSに対して、 以下の操作を行う。(データxまたはキーk) ・insert(S,x) ・delete(S,x) ・search(S,k)Sを表すデータ構造をTとする。第七回 ◯Direct Access Table ・キーをそのままメモリに対応させる ex)T[0]=1, T[2＾15]=20,...…
勉強の続き。http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/ 第四回 ◯クイックソート ・ある数(ピボット)をソートされた位置に順番に移動させる方法 ・入…
年末を利用して、MITのオープンコースでアルゴリズムのお勉強http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/第一回 ◯イントロ ・パフォーマンスより重要な…
