アルゴリズム勉強会 データ構造

前回の課題の講評

学内限定
http://www.ugs.kochi-tech.ac.jp/kutpg/internal/contest/algorithm_workshop1/

データ構造とは

データを扱う構造です。

配列 (Array)

一般的なプログラミング言語なら、どの言語でも利用できるデータ構造です。
配列のサイズを固定した固定長配列と、サイズを動的に変化させられる可変長配列の2種類があります。

特徴

• 要素の追加, 変更, 参照 O(1)
• 要素の検索 O(n)

言語別の実装

C言語

• 言語構造 (固定長)
• 言語構造 (宣言時可変長; C99)

C++

• 言語構造 (固定長)
• vector (可変長)
• valarray (可変長)
• array (宣言時可変長; C++11)

Java

• 言語構造 (宣言時可変長)
• Vector (可変長)
• ArrayList (可変長)

リスト (List)

要素同士を繋げ、一つにしたデータ構造をリストと言います。
要素は前後の要素の参照を持ち、先頭または末尾から辿ることで目的の要素に到達できます。

特徴

• ランダムアクセス不可
• 要素の参照 O(n)
• 要素の追加, 削除 O(1)
• 要素の検索 O(n)

言語別の実装

C++

• list

Java

• LinkedList

スタック (Stack)

後入れ先出し (LIFO: Last In First Out) のデータ構造です。
スタックにデータを追加する push と、スタックからデータを取り出す pop のみの操作が許可され、中間のデータにアクセスすることは出来ません。 *1

特徴

• ランダムアクセス不可
• 要素の追加, 削除 O(1)
• LIFO (Last In First Out)

言語別の実装

C++

• stack

Java

• Stack

キュー (Queue)

先入れ先出し (FIFO: First In First Out) のデータ構造で、初めに入れた要素が初めに出て来ます。
スタックの対になるデータ構造として、セットで解説されることが多いです。

特徴

• ランダムアクセス不可
• 要素の追加, 削除 O(1)
• FIFO (First In First Out)

言語別の実装

C++

• queue

Java

• LinkedList
• LinkedBlockingQueue

両端キュー (Deque)

キューを先頭, 末尾どちらからでも追加, 削除が出来るようにしたデータ構造です。
配列で実装された両端キューは、ランダムアクセスも可能で、配列の上位互換と言えます。

JavaScript, Ruby, Python 等、LL (Lightweight Language) に搭載されている配列の多くは、両端キューとして使えます。

特徴

• ランダムアクセス可能
• 要素の追加, 参照 O(1)
• 要素の検索 O(n)
• 要素の削除 O(n)

言語別の実装

C++

• deque

Java

• ArrayDeque

優先順位付きキュー (Priority Queue)

要素の追加と、優先順位の最も高い要素を取り出すことができるデータ構造です。
キューという名前が付いていますが、先入れ先出し (FIFO: First In First Out) ではありません。

優先順位として、最も一般的なのは要素の大小です。
キューに要素を追加すると、自動的に内部でソートされ、取り出す時は最も優先順位の高い要素が取り出されます。

特徴

• ランダムアクセス不可
• 要素の追加 O(log n) *2
• 要素の取り出し O(1)

言語別の実装

C++

• priority_queue

Java

• PriorityQueue

連想配列

配列の添え字として、数値ではなく、文字列やその他オブジェクトを用いることができる配列です。
Java, C++ をはじめとした、多くの言語で標準ライブラリに搭載されています。

連想配列は、マップ (Map), ハッシュテーブル (Hashtable)*3, 辞書 (Dictionary) などと呼ばれることもあります。

二分木を使った実装と、ハッシュ関数を使った実装の2種類に分けられます。

特徴

二分木による実装

• 要素の参照, 追加, 検索 O(log n)

ハッシュ関数による実装

• 要素の参照, 追加 O(1)
• 要素の検索 O(n)

言語別の実装

C++

• map (二分木)
• unordered_map (ハッシュ関数)

Java

• TreeMap (二分木)
• HashMap (ハッシュ関数)

集合

数学の集合にあたるデータ構造で、セット (Set) とも呼ばれます。
要素が存在するか否かを管理するデータ構造で、重複する要素は一般的に保存されません。 *4

内部は一般的に二分木で実装されており、要素の追加, 検索が高速に行えます。

特徴

• ランダムアクセス不可
• 要素の追加, 削除, 検索 O(log n)

言語別の実装

C++

• set

Java

• Set

課題

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
  連想配列

---

ミス等あれば、編集するかコメント欄でご指摘いただけたら嬉しいです。