前回の課題の講評
学内限定
http://www.ugs.kochi-tech.ac.jp/kutpg/internal/contest/algorithm_workshop1/
データ構造とは
データを扱う構造です。
配列 (Array)
一般的なプログラミング言語なら、どの言語でも利用できるデータ構造です。
配列のサイズを固定した固定長配列と、サイズを動的に変化させられる可変長配列の2種類があります。
特徴
- 要素の追加, 変更, 参照 O(1)
- 要素の検索 O(n)
言語別の実装
C言語
- 言語構造 (固定長)
- 言語構造 (宣言時可変長; C99)
C++
Java
リスト (List)
要素同士を繋げ、一つにしたデータ構造をリストと言います。
要素は前後の要素の参照を持ち、先頭または末尾から辿ることで目的の要素に到達できます。
特徴
- ランダムアクセス不可
- 要素の参照 O(n)
- 要素の追加, 削除 O(1)
- 要素の検索 O(n)
言語別の実装
C++
Java
スタック (Stack)
後入れ先出し (LIFO: Last In First Out) のデータ構造です。
スタックにデータを追加する push と、スタックからデータを取り出す pop のみの操作が許可され、中間のデータにアクセスすることは出来ません。 *1
特徴
- ランダムアクセス不可
- 要素の追加, 削除 O(1)
- LIFO (Last In First Out)
言語別の実装
C++
Java
キュー (Queue)
先入れ先出し (FIFO: First In First Out) のデータ構造で、初めに入れた要素が初めに出て来ます。
スタックの対になるデータ構造として、セットで解説されることが多いです。
特徴
- ランダムアクセス不可
- 要素の追加, 削除 O(1)
- FIFO (First In First Out)
言語別の実装
C++
Java
両端キュー (Deque)
キューを先頭, 末尾どちらからでも追加, 削除が出来るようにしたデータ構造です。
配列で実装された両端キューは、ランダムアクセスも可能で、配列の上位互換と言えます。
JavaScript, Ruby, Python 等、LL (Lightweight Language) に搭載されている配列の多くは、両端キューとして使えます。
特徴
- ランダムアクセス可能
- 要素の追加, 参照 O(1)
- 要素の検索 O(n)
- 要素の削除 O(n)
言語別の実装
C++
Java
優先順位付きキュー (Priority Queue)
要素の追加と、優先順位の最も高い要素を取り出すことができるデータ構造です。
キューという名前が付いていますが、先入れ先出し (FIFO: First In First Out) ではありません。
優先順位として、最も一般的なのは要素の大小です。
キューに要素を追加すると、自動的に内部でソートされ、取り出す時は最も優先順位の高い要素が取り出されます。
特徴
- ランダムアクセス不可
- 要素の追加 O(log n) *2
- 要素の取り出し O(1)
言語別の実装
C++
Java
連想配列
配列の添え字として、数値ではなく、文字列やその他オブジェクトを用いることができる配列です。
Java, C++ をはじめとした、多くの言語で標準ライブラリに搭載されています。
連想配列は、マップ (Map), ハッシュテーブル (Hashtable)*3, 辞書 (Dictionary) などと呼ばれることもあります。
二分木を使った実装と、ハッシュ関数を使った実装の2種類に分けられます。
特徴
二分木による実装
- 要素の参照, 追加, 検索 O(log n)
ハッシュ関数による実装
- 要素の参照, 追加 O(1)
- 要素の検索 O(n)
言語別の実装
C++
- map (二分木)
- unordered_map (ハッシュ関数)
Java
集合
数学の集合にあたるデータ構造で、セット (Set) とも呼ばれます。
要素が存在するか否かを管理するデータ構造で、重複する要素は一般的に保存されません。 *4
内部は一般的に二分木で実装されており、要素の追加, 検索が高速に行えます。
特徴
- ランダムアクセス不可
- 要素の追加, 削除, 検索 O(log n)
言語別の実装
C++
Java
課題
KOJ にある問題を、次のいずれかの言語で解いてください。
- Java
- C++
- C#
- Visual Basic.NET
- J#
- D言語
- Google Go
- Haskell
- F#
- LISP
- JScript.NET
- Groovy
- Whitespace
- Brainf*ck
C言語は、標準ライブラリにデータ構造を持たないため、使用禁止とします。
今回の課題の目的は、データ構造を実装することではなく、データ構造をプログラムで実際に使えるようにすることです。
また、実際の開発において、自分でデータ構造を実装することは、バグを増やすだけでなく、開発時間とコストを無駄に増大させるだけです。*5
http://d.hatena.ne.jp/keyword/%E8%BB%8A%E8%BC%AA%E3%81%AE%E5%86%8D%E7%99%BA%E6%98%8E
問題 URL
http://kut-oj.appspot.com/contest/algorithm_workshop2/
解説, 講評 (学内限定)
http://www.ugs.kochi-tech.ac.jp/kutpg/internal/contest/algorithm_workshop2/
ヒント
- 問題 0
スタック (Stack)
- 問題 1
キュー (Queue)
- 問題 2
優先順位付きキュー
(Priority Queue)
- 問題 3
連想配列
ミス等あれば、編集するかコメント欄でご指摘いただけたら嬉しいです。