目次
- 自己紹介
- AIZU ONLINE JUDGEとは
- やろうと思った経緯
- 問題例
- 所感
自己紹介
- 新卒3ヶ月目Webエンジニア(バックエンド)
- バックエンド未経験で自社開発系企業に入社
- 大学では情報工学を専攻．フロントエンドも少し触る
- 現在は社内の案件に触れて実務を行っている
AIZU ONLINE JUDGEとは？
AOJとよばれるもので、だれでもプログラミングの問題が解けるサイトです。
問題の内容はプログラミングコンテストのようなところで出される、お題に沿ってプログラムをつくって提出→採点をしてくれるサイトです。同じようなサイトに競技プログラミングのAtCoder( https://atcoder.jp/?lang=ja )なんてものもあったりします。
やろうと思った経緯
大学の専攻が情報工学で、よく課題に使われていたサイトだったのでそこで認知
↓
web系の言語でも自分の実力を測りたい！もっと早く正確にコーディングできるようになりたい！
↓
せっかくなので取り組んだ手ごたえをアウトプット
問題例
今回は学生時代よく触れていた「アルゴリズムとデータ構造」という分野で一問取り組んでみたいと思います。
画像の通り分野ごとに何十問と問題があるのですが最初の「1_A:Insertion Sort」(挿入ソート)を解いていこうと思います。
アルゴリズムがあまりわからない方へ
せっかく具体例を出して取り組むのでちょっとした解説を。
今回取り組む問題は"ソート"という配列等の並び替えをする手法の一つです。問題にもなっている挿入ソートの他にもマージソートやクイックソートなど、並び替えひとつとっても手法がいろいろありまして、計算速度やデータの形に合わせて使い分けます。
この挿入ソートは並べ替えの際に自然に思いつく手法で、配列の最初から順に大小を見ていって徐々にソートしていく手法です。
内容
問題はこのようになっていて実行時間の制限や使用メモリの制限もあります。
最初にアルゴリズムの概要、どのようなプログラムを作るのかが書いてあります。
続いて具体的な制約と入出力例があります。
問題説明で理解できなかった場合は具体例を眺めると意外と理解できたりします
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_1_A
実際解いてみる
プログラムはブラウザで直接かけるようになっていて、今回はPHPを使って書いていきます。
他にも多くの言語が対応しており、Web開発の言語はほぼ対応していました。
実際のコード↓
<?php
$input = STDIN; //標準入力
$input_num = trim(fgets($input)); //1行目：要素数
$input_line = fgets($input); //2行目：入力値
$N = $input_num;
$A = explode(" ",trim($input_line));
echo $input_line; //最初の一行
for($i = 1; $i < $N; ++$i){
$v = $A[$i];
$j = $i - 1;
while($j >= 0 && $A[$j] > $v){
$A[$j+1] = $A[$j];
$j--;
}
$A[$j+1] = $v;
//ループごとに進捗を出力
echo implode(" ",$A)."\n";
}
コードを書き終え、”submit”ボタンを押すとこのようにチェックが入ります。問題なければACCEPTEDになり
問題があると指摘されます！今回は問題なく動作したので合格ということになりました。
アカウントを作ることでスコアが蓄積されるのでゲーム感覚で楽しめますよ！
所感
久しぶりにアルゴリズムの問題をといて思ったことは"よりシンプルに早く"という考え方を忘れてはいけないなと思いました。
webアプリケーションを開発している現場だとどうしてもフレームワークに頼っていて今回で言うソートのような裏側で何が動いているのかを知らずに使っている点も多くあると思います。ソートの解説で軽く触れたようにデータによっては相性が悪く相当計算に時間がかかってしまうアルゴリズムもあるので、”この裏では何が起こっているの？”という視点は少なからずエンジニアには必要なのかなと感じました。