全探索(Sum of Three Integers)
はじめに
AtCoderのB問題に「Sum of Three Integers」という全探索をいかに効率的にできるかが本質の問題があり、僕のようなアルゴリズム初心者にはすごく面白い内容だったので紹介したいと思う。
問題内容
二つの整数K,Sと三つの変数X,Y,Zがある。
X,Y,Zは、「0 <= X,Y,Z <= K」であるとき、「X + Y + Z = S」を満たすX,Y,Zの割り当ては何通りであるか。
制約として、「2 <= K <= 2500」、「0 <= S <= 3K」が与えられる。
解法
おそらく、一番最初に思いつくことは3重のfor文だと思う。XとYとZをそれぞれ、0からKまで回し、足し算の結果がSのとき、カウントに1を足していく。
しかし、これでは、Kが99の時点でそれぞれで100の3乗となり、1万回の計算が必要となってくる。もし、Kに2500が割り当てられるとプログラムがタイムアウトしてしまいます。
この問題は、変数を減らすことが解くカギになっていると感じます。例えば、XとYを定数にすれば、Zは、S-(X+Y)となり、Zが条件を満たせば、カウントを増やせばよい。このプログラムでは、計算量がO(K^2)まで減らすことができる。これでタイムアウトを防ぐことはできた。以下がそのプログラムである。
for文の中で使っているif文はiがSの時に無駄に内側のfor文に入らないようにするためである。
このプログラムでも十分、正解になるのだが、一応計算量がさらに減り、O(K)になる方法もある。それは、変数を二つ減らす方法である。
僕のプログラムでは、Xを定数でfor文を回すことで実現した。
Xを固定することで、「Y+Z = S-X」という等式が成り立つ。次にもう一つ、変数を無くしたいのでZをなくなるように調整する。Zは「S-X-Y」であるため、「0 <= S-X-Y <= K」が成り立つ。この不等式から「Y<=S-X」「S-X-K<=Y」という条件が出てくる。これは、Xを固定したときに、Yは最大でどのくらいの数値がでてくるのか、逆に最低でどのくらいの数値が出てくるのかが分かる。これがわかれば、Yは連続した値で出てくるはずなので(最大値ー最低値+1)がXがある定数のときの条件を満たすものとなる。
プログラムは以下となる。
条件は先ほど書いたが、この条件の前にYには0以上K以下というものがある。
なので、Yの最大値はKより大きくならないように、最小値は0より小さくならないように条件をつけている。これで、計算量はO(K)となる。
以上が、「Sum of Three Integers」の二つの解法である。
ナップザック問題(Java)
はじめに
今回は、アルゴリズムの中で「ナップザック問題」を取り扱っていこうと思う。
このナップザック問題を解くうえで、「動的計画法」を使っていく。
ナップザック問題とは
N種類の品物があり、それぞれの品物には大きさと価値が割り当てられている。
この品物を複数選び、大きさの合計がM以下、価値の合計が最大となる品物の組合せを求めよ、というものである。
この問題を力技で解こうとすると、ある品物を入れるか入れないかで全探索しなければならないため、今回の場合は、2^Nとなる。Nが10程度ならばそれほど問題はないが、数百、数千となれば計算量が膨大になりすぎて終わらなくなってしまう。
動的計画法を用いると、この計算量が格段に少なくできる。
動的計画法とは
まず第一に、最も動的計画法の大事な考え方は、「本当に必要かどうかを考えずに、必要になりそうな小さい問題を先にといてストアしておく」である。
分割統治法の逆の手法とも言える。
分割統治法は、大きな問題を解くときに小さな問題に分解し、それぞれを解くことで最終的に全体を解決する。
動的計画法は、必要・不必要関係なく小さな問題を解き、それらを組み合わせ、最終的に全体を解決する。
分割統治法はトップダウン、動的計画法はボトムアップと考えてよいと思う。
しかし、動的計画法を用いるにあたって、注意すべきなのは、
問題をうまく小さな問題に分割すること。しかし、小さな問題が多すぎてはいけないということ。
この二点を気を付ければ、問題なく使うことができると思う。
解き方
まずは、どのように小さな問題に分割するかが重要であり、今回は、品物を1種類にして問題を解いていくという手法を取る。そして、これに対して、ナップザックの大きさは0からMまでを全て試してみる。それらの解をストアしておく。
次に品物を前回のものに新しく1種類足して、同じことをする。
例えば、あるナップザックの大きさxがあるとき、新しい種類の品物のサイズ分を空ける。新しい種類の品物のサイズがyならば、ナップザックの中身をx-yにする。すでに、サイズがx-yを前回の品物1種類だけで埋めたときの結果はストアされているので、あとは、新しいものを足すだけである。もし、このときナップザックの大きさxを前回の品物だけで埋めた場合よりも価値が高ければ更新する、という処理を繰り返せばよい。
文字で書いてもわかりにくいので、プログラムを書いていく。
ナップザック問題のプログラム
具体的に、ナップザックの大きさなどを定義する。
ナップザックのサイズは16、品は5種類、それぞれの重さは2,3,5,7,9で、価値は2,4,7,11,14とする。
プログラムは以下となる。
プログラムで最も注目してほしいのはsolveメソッドである。total配列には、現時点で入っているものの価値の合計が入っており、choiceは最後に選んだ品物が入る。二重for文では、外側で品物を回し、内側でナップザックの全てのサイズについて価値を図っている。
repackTotal = total[j-size[i]] + value[i];
と書いてあるが、これは先ほど説明した新しい種類の品を入れるときにその分、ナップザックを空けて、品を入れ、価値を足しておく。合計の価値はrepackTotalに入れられる。
そして、その後のif文で、前回の同じナップザックのサイズの時よりも価値が大きければ、更新をして、また新しい品物を加えていくということである。
前回の結果をうまく利用して、最大価値を見つけることができているのが分かる。
実行結果は、次のようになった。
入力してください
16
ナップザックの大きさは16
i = 0
total =0 0 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16
choice = -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
i = 1
total =0 0 2 4 4 6 8 8 10 12 12 14 16 16 18 20 20
choice = -1 -1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1
i = 2
total =0 0 2 4 4 7 8 9 11 12 14 15 16 18 19 21 22
choice = -1 -1 0 1 0 2 1 2 2 1 2 2 1 2 2 2 2
i = 3
total =0 0 2 4 4 7 8 11 11 13 15 15 18 19 22 22 24
choice = -1 -1 0 1 0 2 1 3 2 3 3 2 3 3 3 3 3
i = 4
total =0 0 2 4 4 7 8 11 11 14 15 16 18 19 22 22 25
choice = -1 -1 0 1 0 2 1 3 2 4 3 4 3 3 3 3 4
品物4、価値14を詰め込む
品物3、価値11を詰め込む
価値の合計 = 25
どんどん更新されていき、totalの中で最も数の多いのが最大価値の入れ方となっている。この場合は、i=4のときのtotal=25である。
このナップザックには何が入っているのかを分析するために変数choiceがある、totalが25のときの、choiceは4となっているので、品物4が入っていることが分かる。品物4は価値14であるから、totalから14を引くと、11となる。では、totalが11の時のナップザックには何が入っているのかを調べると、品物3であることが分かる。ちなみに、最大価値11の作り方は他にもあるが、最新のものを出力するようにしたので、品物3,4となっている。
以上がナップザック問題に対して、動的計画法を使った解法である。
参考にしていただけるとありがたいです。
Servlet/JSP 応用編05 商品の検索と登録
はじめに
今回の記事では、サーバにある商品を検索したり、商品を登録するプログラムを書きたいと思う。
方法としては、商品の全探索と変わりはあまりない。select文を使いましょう。あとは、where句で条件を足すだけで詳細に検索をすることができる。しかし、このままでは、完璧に商品名を打たないと検索結果にでてこなくなる。これでは、非常に使いにくい検索になってしまう。そこで、like演算子とワイルドカードを用いる。使い方は、
where 列名 like '%キーワード%'
で良い。「%」はワイルドカードの一つで、0文字以上の任意の文字列を表す。つまり、「%キーワード%」といった使い方をすれば、「キーワード」という言葉に前後何か言葉があっても結果としてでてくるのだ。今回はこれを利用したプログラムを書いていく。
検索プログラムの作成
中身の処理を書く前に、検索をしやすいように専用の欄を作成する。プログラムは以下の通りになる。
ここで最も重要なのは、テキストボックスである。このボックスに入力されたテキストがjavaファイルに処理を送るためである。なので、name属性には、分かりやすく、「keyword」と名前を付けましょう。
次は、実際に処理をするためのサーブレットの作成をする。先にプログラムを貼っておく。
データベース接続までは前回の記事と全く同じなので、解説を省略する。
最初に大事なのは、keyword変数にgetParameterメソッドで、「keyword」の要素をとり、格納している。つまり、この変数に、検索内容を格納しているということである。
次に、その検索ワードにはじめに記した、like演算子とワイルドカードを加え、データベースから検索しなければならない。
なので、prepareStatementでSQL文を書いている。「?」マークがあるが、これはプレースホルダを利用している。「?」マークの場所はあとから値を入れることができる。そして、値を入れるためには、setStringメソッド、setIntメソッドを使う。引数は二つあり、一つ目には、何個目の「?」に値を入れるのかを指定する。今回の場合は一つしかないので、「1」と書く。次に、二つ目の引数には、入れたい値を書く。今回はキーワードの中身を入れる。
では、実際にブラウザで結果を見てみましょう。
「軍艦」というキーワードを指定する。ワイルドカードを使わない検索だと、「軍艦」という商品がない限りはヒットすることはない。
結果を見てみる。
ワイルドカードを使用しているため、「〇〇軍艦」という結果もでてきた。これで、like演算子がどのようなものか分かっていただけたかと思う。
登録プログラムの作成
次は、商品をデータベースに登録するプログラムを作成したいと思う。このプログラムで知ってほしいのは、「executeUpdate」メソッドである。
追加、更新、削除の場合は検索と違い、Resultsetを利用した処理を記述するわけではないので、処理が成功したかどうかを知ることができない。そこで、代わりに使用するのが、executeUpdateメソッドである。このメソッドの返り値は、SQL文によって、変更された行数であるため、0行が返ってきたときには、処理は失敗しているということが分かる。
では、実際に使っていく。まずは、JSPファイルの作成をする。
大事なのは、商品名のテキストボックスと、価格のテキストボックスであり、ここで入力されたものでSQL文を作成し、データベースに追加をする。そのような処理を行う。サーブレットを下記に載せる。
検索プログラムと同じように、getParameterメソッドで入力内容を変数に格納する。prepareStatementメソッドでは、プレースホルダを二つ使う。入力内容が二つあるためである。今回の場合は、一つ目は、商品名であるからsetStringメソッドを、二つ目は、価格であるからsetIntメソッドを使う。プレースホルダに、入力が完了すれば、そのSQLをデータベースに送る。変更が起きれば、変数lineに変更が起きた行数が返り値として代入される。それが0より大きければ、「追加に成功した」と画面に出すことにする。では、実行する。
商品名は「鮭」、価格は「1000」で入力する。追加ボタンを押すと、コマンドプロンプトに成功のメッセージが届いた。
そして、結果を見るために、全探索をすると、
今までの商品にプラスして、鮭がたされていることが分かる。
以上で、検索と追加のプログラムを解説した。
Servlet/JSP 応用編04 Javaとデータベース
はじめに
今回は、Javaプログラムとデータベースを操作する方法を解説したいと思う。
まず、Javaからデータベースに操作するには、JDBCを使わないといけない。これを利用することで、データベース管理システムにSQL文を発行して、結果を取得できる。さらに、他の利点としては、データベース間の違いを吸収してくれる点である。データベースは様々あり、それぞれ性能が違う。しかし、そのようなことを気にせずに操作できるようにしたのがJDBCである。
データベース接続
データベースを操作するには、接続しなければならない。接続するのにjava.sql.Connectionクラスのインスタンスが必要となる。また、java.sql.DriverManagerのクラスメソッドも必要。使い方は以下の通りになる。
Class.forName("JDBCのクラス名");
Connection conn = DriverManager.getConnection("接続文字列" , "ユーザ名" , "パスワード");
このように、JDBCのクラス名や他の情報が必要となる。なので、接続する情報を変更しないといけないとき、広範囲の修正が必要となる。しかし、現在のJDBC2.0では、データソースという機能が増えた。データソースというのは、アプリケーションサーバを利用してデータベースに接続する仕組みである。
利点は2つある。
1つ目は、接続に必要な情報をアプリケーションサーバの設定ファイルに記述することができる。なので、情報の変更が簡単、または、容易になる。
2つ目は、データベースの接続の際に、再利用することで、性能を向上させることができる。
では、データベースにアクセスする手順を説明していく。
簡単に言うと、データベースに接続し、SQLを作成、実行。結果を取得、必要な処理の実行。最後に切断を行う。
一つ一つに様々なメソッドを使う。実際のプログラムの中で解説していく。
今回作成するプログラム
今回は、データベースに接続する練習なので、商品一覧を取得し、表示するサーブレットを作成する。つまり、サーブレットの中で、
select * from product;
を実行すればよい。
実際に書いていく。
まず、データベースを扱ううえで必要なクラスなどをインポートする。
try文の中は、最初にInitialContextオブジェクトを生成。これにより、データやオブジェクトを名前で参照することができる。しかし、これだけでは意味がないので、lookupメソッドを使う。引数には、データソースのオブジェクトを入れる。ここで、注意があり、lookupメソッドの返り値はObject型であるから、キャストが必要となる。そして、DataSource型の変数に入れれば、あとは、接続するだけである。getConnectionを使用すれば、接続できる。接続が終われば、次は、SQLの作成と実行である。実行するためにPreparedStatementオブジェクトを取得する。そして、このSQL文をexecuteQueryメソッドを実行し、ResultSetオブジェクトとして取得する。
これで、データを取得できたので、while文の中で、nextメソッドを使用し、行ごとに、IDとname、priceの値を取っていく。nextメソッドの返り値はbooleanで、データがなくなれば、falseで帰ってくる。最後には、closeメソッドで、データベースとの接続を切る。
実際に実行すると下記のようになった。
10 : つぶ貝 :100
11 : サラダ軍艦 :150
12 : ねぎとろ軍艦 :150
13 : ねぎとろ巻 :150
14 : アボガド巻 :150
前の記事で、idが10より下、14より上を消したので全部のデータが表示されていることが分かる。
おわりに
今回は、データベースに接続する方法を紹介した。次回からは、Javaプログラムから商品を検索、追加などをしていこうと思う。
Servlet/JSP 応用編04 Javaとデータベース
はじめに
今回は、Javaプログラムとデータベースを操作する方法を解説したいと思う。
まず、Javaからデータベースに操作するには、JDBCを使わないといけない。これを利用することで、データベース管理システムにSQL文を発行して、結果を取得できる。さらに、他の利点としては、データベース間の違いを吸収してくれる点である。データベースは様々あり、それぞれ性能が違う。しかし、そのようなことを気にせずに操作できるようにしたのがJDBCである。
データベース接続
データベースを操作するには、接続しなければならない。接続するのにjava.sql.Connectionクラスのインスタンスが必要となる。また、java.sql.DriverManagerのクラスメソッドも必要。使い方は以下の通りになる。
Class.forName("JDBCのクラス名");
Connection conn = DriverManager.getConnection("接続文字列" , "ユーザ名" , "パスワード");
このように、JDBCのクラス名や他の情報が必要となる。なので、接続する情報を変更しないといけないとき、広範囲の修正が必要となる。しかし、現在のJDBC2.0では、データソースという機能が増えた。データソースというのは、アプリケーションサーバを利用してデータベースに接続する仕組みである。
利点は2つある。
1つ目は、接続に必要な情報をアプリケーションサーバの設定ファイルに記述することができる。なので、情報の変更が簡単、または、容易になる。
2つ目は、データベースの接続の際に、再利用することで、性能を向上させることができる。
では、データベースにアクセスする手順を説明していく。
簡単に言うと、データベースに接続し、SQLを作成、実行。結果を取得、必要な処理の実行。最後に切断を行う。
一つ一つに様々なメソッドを使う。実際のプログラムの中で解説していく。
今回作成するプログラム
今回は、データベースに接続する練習なので、商品一覧を取得し、表示するサーブレットを作成する。つまり、サーブレットの中で、
select * from product;
を実行すればよい。
実際に書いていく。
まず、データベースを扱ううえで必要なクラスなどをインポートする。
try文の中は、最初にInitialContextオブジェクトを生成。これにより、データやオブジェクトを名前で参照することができる。しかし、これだけでは意味がないので、lookupメソッドを使う。引数には、データソースのオブジェクトを入れる。ここで、注意があり、lookupメソッドの返り値はObject型であるから、キャストが必要となる。そして、DataSource型の変数に入れれば、あとは、接続するだけである。getConnectionを使用すれば、接続できる。接続が終われば、次は、SQLの作成と実行である。実行するためにPreparedStatementオブジェクトを取得する。そして、このSQL文をexecuteQueryメソッドを実行し、ResultSetオブジェクトとして取得する。
これで、データを取得できたので、while文の中で、nextメソッドを使用し、行ごとに、IDとname、priceの値を取っていく。nextメソッドの返り値はbooleanで、データがなくなれば、falseで帰ってくる。最後には、closeメソッドで、データベースとの接続を切る。
実際に実行すると下記のようになった。
10 : つぶ貝 :100
11 : サラダ軍艦 :150
12 : ねぎとろ軍艦 :150
13 : ねぎとろ巻 :150
14 : アボガド巻 :150
前の記事で、idが10より下、14より上を消したので全部のデータが表示されていることが分かる。
おわりに
今回は、データベースに接続する方法を紹介した。次回からは、Javaプログラムから商品を検索、追加などをしていこうと思う。
Servlet/JSP 応用編03 データベース
データベースとは
データの集まりのことである。また、ただの集まりではなく、検索、更新が行いやすい形式に整理されている。このデータベースを構築、操作するソフトウェアがデータベース管理システム(DBMS)と呼ぶ。
データベースの表をテーブルという。テーブルの横方向に並んだ格子群を行、縦方向に並んだ格子群を列という。図で表すと次のようになる。
番号 | 品名 | 価格 |
1 | あああ | 100 |
2 | いいい | 200 |
3 | ううう | 300 |
SQL
SQLとは、データベースを操作するためのプログラミング言語である。SQLを使えば、テーブルの作成、行の追加、検索などが可能となる。また、SQLで記述したひとまとまりの処理のことをSQL文と呼ぶ。このSQL文をデータベースに対し、実行し、結果を利用者に返す。
テーブルの作成、データの操作
データベースの中にテーブルを作成する。テーブル名は「product」とする。
テーブルを作成するには、create table文が必要となる。書き方は下記の通りである。
create table テーブル名(
列名1 データ型 制約,
列名2 データ型 制約,
・
・
・
);
列の定義はカンマで区切り、最後にはセミコロンをつける。データ型は格納するデータの種類を指定する。次に、制約とは、列やテーブルに格納するデータに対して、制限を設定するための機能。
データの追加には、insert文を使用する。使用例は以下である。
insert into テーブル名 values(列1の値, 列2の値,...);
テーブルの削除には、drop table文を使う。使用例は以下である。
drop table テーブル名;
では、実際にテーブルを作成し、データを追加していく。プログラムは以下である。
1行目はdrop table文を使用している。意味は「productというテーブルがあるなら、削除する」であるが、存在していないので、意味はない。
次に、create table文を使用。列名は「id」「name」「price」で、型は「int」、「varchar(100)」、「int」である。「varchar(100)」は可変長100桁の文字列である。制約は、「auto_increment , primary key」、「not null」、「not null」である。
「auto_increment」は行を追加したときに、自動的に番号を付けてくれるというものである。「primary key」は主キー制約である。idが主キーになるということである。「not null」はこの列をnullにできないことを示している。
次に、insert文を使い、データ追加していく。idにはnullを、nameには、適当な品を入れる。priceは価格を入れていく。
では、テーブルが作成され、データも追加できたので、このテーブルから検索を行う。検索には、select文を使う。使い方は以下である。
select 列名 from テーブル名 [where 条件]
今回は簡単にテーブル全てを検索してみる。
select * from product;
「*」は全てという意味である。「product」というテーブルから全て検索することである。結果は以下のとおりである。
追加したデータがすべて表示されているのが分かる。
次は、条件をつけて検索をする。
select * from product where id >= 15;
これは、idが15以上の全てを検索するというもの。結果は以下となる。
「ID」を見ると、しっかりと15以上のものが表示されている。
次は、データを更新する。
update テーブル名 set 列名=値 [where 条件];
では、nameが「いくら」のpriceを120にする。
update product set price=120 where name='いくら';
と、書けば、いくらの値段が120となる。
実際に動かしてみる。
ちゃんと更新している。
最後に削除してみる。delete文を使う。
delete from テーブル名 [where 条件];
select文などと同じように使うことができる。idが10より小さいものと、idが14より大きいものを消す。
delete from product where id<10 or id>14;
これで、先ほどの条件に当てはまるデータを消すことができる。結果を見てみる。
ちゃんと消されていることが分かる。
おわりに
今回は、データベースのテーブル作成とデータの操作を紹介した。基本的なものばかりだが、これでほとんどの操作が可能となる。次回からは、このデータベースとjavaを連携されていく。
Servlet/JSP 応用編02 HTTPのリクエスト
はじめに
今回は、HTTPのリクエストについて解説していこうと思う。普通は、HTTPのリクエストの情報は隠されていて、直接操作することはない。しかし、デバッグの際に問題解決に役立つことがある。
これを利用すれば、POSTリクエストの内容も、メッセージとして表示される。
メソッド
様々な情報を取得でき、そのうちのいくつかを紹介しようと思う。
まず、リクエストラインを取得でき、「getMethod」では、リクエストの種類、「getRequestURI」で、リクエストされたURIを取得できる。ヘッダの情報も取得でき、「getHeader」で指定した名前のヘッダフィールドを取得、「getHeaderNames」ですべてのヘッダフィールドの名前を取得できる。
作成するプログラム
リクエスト情報を取得するサーブレットを作成する。こういう機能があるのだなと思っていたければよい。
requestクラスのメソッド「getRequestURL」「getHeader」「getRemoteAddr」を使用している。HostとUser-Agentのヘッダ情報を取得しており、Hostは、サーバの情報、User-Agentは、ブラウザの種類を表す。「getRemoteAddr」はリクエスト送信元、つまり、ユーザのIPアドレスを表示する。
実行結果は以下のようになった。
ちゃんと表示されていることが分かる。
おわりに
今回は簡単にHTTPリクエストについて紹介した。次回はサーブレット/JSPとは一瞬ずれて、「データベース」について紹介したいとおもう。