[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
318
質問
1
票
2
回答
1,433
閲覧数
二分探索木の平均の計算量を示す方法について
二分探索木の平均の計算量を示す方法について
下記画像の結果よりすべてのnについてT(n)<4logn+1が示せたことになり、木の平均深さがO(logn)であることがわかるそうです。
下記画像の二分探索木の平均の計算量を示す方法について5点不明な箇所がございます。
⑴ T(n)<= alogn+bを仮定する理由について
...
0
票
1
回答
160
閲覧数
コーディングテスト問題「Triangle」について
コーディングテスト練習サイトCodilityの「Triangle」という問題について、
問題の理解とコードがなぜあるケースでincorrectになるのかわからず困っています。
Triangle coding task -Learn to Code - Codility
上記の問題について日本語で解説された記事
テストケースについて以下の注意が表示されましたが、
...
1
票
1
回答
216
閲覧数
数式の変形の過程について
下記数式についてです。
上の式から下の式に変形する過程や数学的な性質が理解できません。
数学に弱くお恥ずかしいですのですが、ご解説いただければ幸いです。
▼分からない箇所
下記の1/n^2Σnが1/nΣ1になる式(下記画像の1行目、2行目)になる箇所がわかりませんでした。
また、最終式についてなのですがシグマ通しの足し算はシグマの左側(今回でいうところの1/n^...
0
票
2
回答
400
閲覧数
コーディングテストにおけるコードのTIMEOUT ERRORについて
オンラインでコーディングテスト練習ができるCodilityのMaxProductOfThreeという問題のコードですが、テストケースが全て正解でもDetected time complexityがO(N**3)だったので、テストスコアが44%/100%と表示されました。
(参考)MaxProductOfThreeについて日本語で書かれた記事
参考記事で書かれているO(N)...
0
票
2
回答
213
閲覧数
コードのパフォーマンスについて
コーディングテスト練習サイトCodilityの「FrogRiverOne」という問題で、書いたコードのパフォーマンスが悪かったのですが、どのように改善すれば良いのでしょうか。
パフォーマンスの良いコードの書き方がよくわかっていないので、学べるサイトや教材などももしおすすめのものがあれば教えていただきたいです。
FrogRiverOne coding task - Learn to Code - ...
0
票
1
回答
196
閲覧数
アットコーダーの問題について(Colorful Subsequence)
下記アットコーダーの問題がわかりません。
https://atcoder.jp/contests/agc031/tasks/agc031_a
解説やACの方のコードを見てみましたが26サイズのint配列にc[各文字 - 'a']++を
し、A.答え *= c[i]を繰り返すと求めるべき出力になるのか理解できませんでした。
噛み砕いて解説いただけると幸いです。
ーー
問題文
長さ Nの文字列 ...
0
票
1
回答
213
閲覧数
コーディングテスト問題「FrogRiverOne」について
コーディングテスト練習サイトCodilityの「FrogRiverOne」という問題について、問題の理解とコードがなぜあるケースでincorrectになるのかわからず困っています。
FrogRiverOne coding task - Learn to Code - Codility
上記のFrogRiverOneについて日本語で書かれた記事
以下問題文を原文引用しました。...
1
票
2
回答
213
閲覧数
swift playgrounds while文のネストについて
swift playgroundsで何度目かの学び直しをしています。
画像のとおりにコードを打ちまして、赤い宝石までは順調に行くのですが、宝石のマスで止まってくれず、そのまま素通りしてしまいます。
while文のネストが良くないのでしょうか?
!isOngem が解除されたら(宝石のマスに来たら)外枠のwhile文から抜けてcollectGemしてほしいのですが、そのまま真っ直ぐ歩いてしまいます。
...
0
票
1
回答
140
閲覧数
分割統治法を利用した数式についてです。
分割統治法についてです。
下記画像の再帰的に代入すると4^2 T(n/2)=....4^log2^n T(1)=n^log2^4 T(1)と数式が変化する過程、理由がわかりません。
数学に弱く数学的な知見が不足しているかもしれません。
噛み砕き解説いただけると幸いです。
参照:データ構造とアルゴリズム
1
票
1
回答
351
閲覧数
テストケースに通らない理由がわかりません。
テストケースが通りません。
入力結果を何個か確認したところあってそうなのですがどこがテストケースにひかかっているか不明です。
解説いただければ幸いです。
▼問題文
正整数
A,Bが与えられます。
Aも Bも割り切る正整数のうち、N番目に大きいものを求めてください。
なお、与えられる入力では、
Aも Bも割り切る正整数のうち N番目に大きいものが存在することが保証されます。
制約
...
0
票
1
回答
97
閲覧数
Pythonでの論理演算の吸収律を適用するアルゴリズムの実装について
Javaで実装した、論理演算の吸収律を適用する以下のようなアルゴリズムをPythonに書き直しております。
1 Vector matrix = [ [a], [a, b], [a, c] ];
2 for (int i = 0; i < matrix.size(); i++) {
3 Vector element_left = matrix.get(i);
4
5 for (...
6
票
7
回答
793
閲覧数
12ヶ月の中の複数月の平均を求めるアルゴリズム
お世話になります。
業務で、今度の四月から開始される『働き方改革』の中に、複数月の平均が80時間を超えてはならないと
いうのがあり、それを求めるためのツールをAccessで作成しています。
四月から始まり、三月で終わる一年の期間の中で、二ヶ月以上の連続した組み合わせ(4-5,4-5-6,4-5-6-7~1-2-3,2-3まで)の平均を算出するのですが、...
1
票
2
回答
145
閲覧数
ZIPコンテナを効率よく読み込むには?
通信用語の基礎知識さんのZIPコンテナの記事を見て、自分でZIPコンテナファイルの実装を作ろうと考えているのですが、ZIPファイルを解凍せずにZIPファイルの中身を読み込んだり書き込んだりするにはどうすればいいのでしょうか?
(ZIPコンテナというのはePubで使われている規格です。)
...
12
票
4
回答
1,561
閲覧数
クイックソートの2種類の実装法で実行速度に顕著な違いが出る
(QuickSort:GeeksforGeeksを参照)
QuickSortの大枠を、
/* low --> Starting index, high --> Ending index */
quickSort(arr[], low, high) {
if (low < high) {
pi = partition(arr, low, high)
...
5
票
1
回答
240
閲覧数
デザインパターンのIteratorについて
プログラミング初心者でJavaでIteratorについて学んだのですが、
・Iteratorには大まかに二つ役割があって、それはIteratorクラスとAggregateクラスの二つなのですが、実際にJavaで提供されているAPIはIteratorがjava.util.Iteratorクラス(Enumerationというのもありました)、AggregateがArrayListやMap、...
1
票
1
回答
315
閲覧数
関数のグラフをプロットする際に、特異点の周辺を取り除く方法
陽に y = f(x) の形で表されている関数のグラフを (x, y) 平面上に描くことを考えます。ただし x_min ≦ x ≦ x_max の範囲に限定してプロットするとします。
素朴には、x_min から x_max まで少しずつ x を変更しながら (x, f(x)) を計算して、それらの点を線分で繋ぐとグラフが描けそうです。
...
6
票
1
回答
724
閲覧数
量子コンピュータによってソートは速くなりますか?
ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
1
票
1
回答
522
閲覧数
ソートに必要な最低計算量は n log n ではないのか?
長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?
8
票
2
回答
2,747
閲覧数
DOMが書き換わった後ブラウザはどのように再描画していますか?
ブラウザで HTML/CSS を読み込んでページを描画した後、もし JavaScript によって動的に DOM が書き換わったら、ブラウザはページの再描画をしなくてはなりません。
素朴に考えるとページの描画にかかるコストは無視できません。DOM がちょっと変わっただけで要素のレイアウトが変わりえますし、テキストの折り返しが変わって更にレイアウトが変わることもありそうです。
しかし多くの場合、...
6
票
1
回答
775
閲覧数
動画をバージョン管理するための diff アルゴリズム
Git などのバージョン管理ツールの発展の背後には「テキストデータは行単位で簡単に差分が取れ、しかもどのような差分なのか閲覧しやすい」という特徴があるように思います。
逆に音声、画像、動画といったバイナリデータでは "良い感じ" の差分が取りづらく、定期的なバックアップを使ったバージョン管理より高度なバージョン管理がやりにくそうです。個人的に動画編集をしていると、動画に対して Git ...
6
票
0
回答
288
閲覧数
Git のマージ戦略 "resolve" とはどのような戦略ですか?
git merge のマージ戦略には resolve というものがあります。
resolve
This can only resolve two heads (i.e. the current branch and another branch you pulled from) using a 3-way merge algorithm. It tries to carefully ...
10
票
1
回答
6,270
閲覧数
Git の 3-way merge とは具体的にどのようなアルゴリズムですか?
Git のドキュメントによると、git merge は内部で 3-way merge を行います。
2-way merge だと不都合があるのは分かるのですが、ではこの 3-way merge は具体的にどのようなアルゴリズムでマージをするのでしょうか? 厳密には 3-way merge と recursive 3-way merge というものがあるようですが、ここでは Git ...
4
票
1
回答
123
閲覧数
ruby で ordered hash 的なことがやりたい
ruby で、木構造で実装される Map データ構造が扱いたくなりました。以下の条件を満たすクラスはありますか?ないし、実装したライブラリなどはありますか?
h.set(key, value) で値を store でき、 h.get(key) にてそれを取得できる。それらは O(log(N)) 以下で実行できる
h.find_sup(key) にて、 key よりも大きな最小のキーと、...
1
票
2
回答
165
閲覧数
ランキングの取得と更新の計算量のうち、最悪の計算量を最小化するには?
ゲームのスコアランキングを考えます。各ユーザーに対して、スコアがただ一つ紐づいているとします。このとき、あるユーザーが与えられた時、全ユーザーの中で何番目のスコアを持っているかを知りたいとします。
このようなランキングのデータ構造は、取得と更新の計算量がトレードオフの関係にあると思います。
というのも、例えば各ユーザスコアデータについて、愚直にユーザーをキーにしたハッシュテーブルに入れておき、...
5
票
0
回答
135
閲覧数
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?
グラフ構造、たとえばツリー構造を探索することを考えます。
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。
この時、
幅優先探索はしばしばキューを用いて
深さ優先探索はしばしばスタックを用いて
それぞれ実装されます。
これはちょうど、
各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う
次のノードを pop() ...
5
票
1
回答
245
閲覧数
ランダムに複数引いた通路の幅が同じになるように整形する方法
ランダムでダンジョンのマップを作成しようとしています。
上の画像のように2つの部屋があり、その間を、2マスの幅がある通路でつなぎます。
通路の始点、終点や折れ曲がる地点はランダムで決まります。
さらに通路を追加します。
二度目以降に通路を追加する際、以前に引いた通路を気にせずに引くので、以前に引いた通路と一部が重なったり、隣り合ったりする場合があります。
こうして2、3回通路を引いた後で、...
1
票
1
回答
714
閲覧数
ビットDPの思考回路について
以下のコードのアルゴリズムの思考回路がよくわかりません。
ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません(なぜDPが成立するのかがわからない)。
また、どのようにすればこのような思考でコードをかけるのでしょうか?
どなたか分かる方はいらっしゃるでしょうか?
コード元: 第16回日本情報オリンピック 予選4
#include<...
2
票
2
回答
836
閲覧数
線分群から、閉図形の数を数える方法を教えて下さい。
仕様1:2次元
仕様2:線分と線分の交差は、気にしません。
目的:輪(環)がいくつあるか知りたい。
例1
input : 線分1 [ 0, 0], [10, 0]
線分2 [10, 0], [ 0,10]
線分3 [ 0,10], [ 0, 0]
線分4 [-5, 0], [-5,10]
output : 閉図形の数=1
: ...
-4
票
3
回答
1,333
閲覧数
お釣りの札と硬貨の枚数をもとめたい
お釣りの札と硬貨の枚数をもとめたいです。Rubyで解きたいのですがやり方がわかりません。
468円の買い物をして1万円札を出したときの実行結果は以下の通りになります。
五千円札の枚数 = 1
千円札の枚数 = 4
五百円玉の枚数 = 1
百円玉の枚数 = 0
五十円玉の枚数 = 0
十円玉の枚数 = 3
五円玉の枚数 = 0
一円玉の枚数 = ...
2
票
1
回答
425
閲覧数
ErrorSortがなぜ、役に立たないのか教えてください。
まず最初にErrorSortの記事の記事を読んでください。
ソートアルゴリズムには一番実装が簡単なソート方法にして、効率の悪さに反して実装例が多いバブルソートや要素の値の数が少ないときにはよく使われるバケットソート、ネタソートの中ではいちばん有名なボゴソートなどがありますが、
エラーソートはなぜ作者がネタソートだと言っているのでしょうか?
パット見役に立ちそうなかかれ方をしているのですが、...
3
票
5
回答
1,423
閲覧数
自身の要素に重複が無い昇順の配列同士で、共通している要素を求めたい
C言語についての質問です。
二つの配列A,Bがありそれぞれに整数が格納されていて、配列の中の数は昇順にソートされていて、配列Aの中には重複する数がなく、それは配列Bについても一緒である。
ただし、配列AとBのサイズは同じとは限らない。
それを踏まえて配列AとBの中には重複する数があり、その重複して含まれる数を出力するプログラムを教えてください🙏
0
票
2
回答
645
閲覧数
数列を許容範囲でグループ化(分割)する方法を教えて下さい。
例
input 数列 {1, 2, 2.01, 3} と 許容誤差(範囲)=0.1
output {1} {2, 2.01} {3}
①タイトルで意味が通じますか?正式名称があれば教えて下さい。検索語が思いつきませんでした。
②outputを、区切り1.5と2.5(2.8でも可)にする予定です。
③特に言語にこだわりません。おすすめのページがあれば教えて下さい。
よろしくお願いします。
...
0
票
3
回答
3,144
閲覧数
幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?
質問
グラフ構造に対して幅優先探索を再帰関数を使って実装することはできるのでしょうか?
深さ優先探索の場合、スタックか再帰関数を使って実装ができます。
一方で深さ優先探索の場合、キューを使って実装することはできたのですが、キューを使わずに再帰関数で実装することができずに困っています。
参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、...
5
票
2
回答
2,343
閲覧数
負の重みを含んだ最長経路の求め方
皆様のアイデアを頂戴したいです。
仕事上の目的で、下のような有向グラフの最長経路を求めたい
と考えております。①から⑤までです。
実際のグラフはもっと複雑です。ですので総当たりは難しいです。
最初ダイクストラ法を用いようと考えましたが
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路
が求められない。
②負の重みがある。
ため断念しました。
...
3
票
1
回答
609
閲覧数
O(N/k)をk=1からk=Nまで計算したときの計算量
やりたいこと
O(N/k)の計算をk=1からk=Nまで計算するときの計算量を計算したいです。
(O(オー)はオーダー記法です。)
そのために下記のように求めようとしているがわからず困っている
計算量を計算するために大体のオーダーを求めると下記等式が成立するようです。
これは、どうやって計算すればよいのでしょうか。
ちょっとぐぐってみたら、
...
4
票
1
回答
581
閲覧数
どのような多面体かを知るコード
多面体を作る方法について
PythonでもCでもMatlabでも言語は問いません。
例えば正20面体に関する以下のようなデータがあるとします。
このデータは正20面体の各頂点0から11に関してどの3点でひとつの三角形、つまり正20面体のひとつの面を作っているかを示します。
この画像のように頂点をつなげていくことができます
データ1
6 4 0
4 9 0
9 3 0
3 11 0
...
3
票
2
回答
1,691
閲覧数
8パズルで、最初にシャッフルさせる時の考え方
8パズルで、解けないような配置になることはありますか?
・最初にシャッフルさせる場合、単純にランダム配置させるだけでは駄目?
123
456
78
経緯
・ネットに掲載されていた8パズルを試しているのですが、どうしても解けないときがあります
・コード内容によっては、解けない8パズルが出来ることもある?
分からないこと
・参考にしているコードが、そもそも正しいか分からない
・...
2
票
0
回答
234
閲覧数
クイックソートにおけるデータ列のソートの仕方について
はじめまして。
アルゴリズム初心者でクイックソートでつまづいております。
{5,3,2,6,4,1,3,7}というデータ列で、真ん中の4を基準値(ピボット)とした場合(6と4の間にパーテーションを設けた場合、)どのように(昇順)ソートされていくか順を追ってご説明頂けますと幸いです。
※自分で試した場合、なぜか昇順でソートすることができませんでした。(1が最左端に来ず、並び順が{3,3,2,1,:...
6
票
1
回答
873
閲覧数
C++での自己参照構造体におけるポインタにおいて
C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照)
この場合、p,l,rの型はNodeではなくてNode*です。
これはNodeではいけないのでしょうか?
ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、
ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。
struct Node {
int key;
...
3
票
2
回答
919
閲覧数
任意の辞書で「もしかして」検索機能を提供するライブラリまたはアルゴリズム
誤字を検出して正解の単語をサジェストする、いわゆる「もしかして」検索を実装しようとしています。
使用する正解の単語コーパス(以下『辞書』)を検索対象の項目ごとに切り替えて精度を上げる運用を考えています。
(例えば氏名の項目には『氏名データベース』から、注文の項目には『自社の取扱い商品名リスト』から生成した辞書をそれぞれ割り当てます)
...
1
票
1
回答
934
閲覧数
pythonによるFFTの実装
pythonでFFT(高速フーリエ変換)を実装しようと思っています
コードはご覧の通りです
(FFT_sort.py)
import numpy as np
def sort(N):
flag = ~(N & (N - 1))
if flag != -1:
return None
result = np.zeros(N, dtype=np....
1
票
1
回答
366
閲覧数
ユークリッドの互除法でZeroDivisionErrorが発生する原因について
ZeroDivisionError: integer division or modulo by zero
以下がコードです.
def Euclidean_algo(m, n):
while m%n != 0:
m = n
n = m%n
else:
return n
m = int(input('the bigger int ...
1
票
1
回答
565
閲覧数
DeepLearningの学習データ(jpeg、raw)と組み込みシステムについて
私は画像を使ったディープラーニングについて勉強しています。
今回疑問があり皆様の意見を聞きたく投稿しました。
一般的にWebの画像認識に使用する学習データは容量を少なくする為、jpeg画像が多いと思います。
しかし、組み込みシステムで使用するカメラ画像は圧縮せずにraw形式の画像をメモリに保存し認識処理すると思います。
ここで、Web上の学習モデル(jpeg)を使用した場合、...
1
票
5
回答
1,157
閲覧数
AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。
久々にやったAIZU ONLINE JUDGEのこの問題で困ったことが起こったので、質問させていただきます。
問題を解くコードをPython3で書いたのですが、何回やってもTime Limit Exceedと表示されます。証拠となるソリューションはこのリンクにあります。
何が原因で、その解決方法はないのでしょうか?
わかる方、いましたら教えてください。
なお、コードは以下のとおりです。
...
0
票
1
回答
4,007
閲覧数
ポインタの値をバブルソートで並べ替えたい
C言語でポインタで定義した値を昇順に並べ替えたいので,バブルソートの関数を作成しています.
現状では,下記の関数を作成しましたが,ポインタの書き換えができていないためか元の値とは関係ない数値(0.00,-737.05,67662660000000000.00など)が出力されます.
やりたいことは「一つのポインタで定義している全ての値を昇順に並べ替える」ということなので,
...
1
票
1
回答
161
閲覧数
numpyで2つの三次元座標点列の引き当て
numpyで2つの三次元座標点列の引き当てをできるだけ高速に行いたいのですが、行き詰まっています。
<前提>
numpyのround()とbuiltinsのround()は挙動が異なります。
(これ自体は質問の主旨ではありませんが、これについても解説いただけると大変ありがたいです。)
>>> print(round(411105.886185, 5))
...
2
票
2
回答
542
閲覧数
numpyで2つの配列をシーケンシャルに比較したい
ある配列 a のサブセットの配列を b としたときに、 b の各要素が a の何番目にあるか、を調べたいです。
具体的には以、下のコードを numpy を使って高速に実現したいのですが、やり方がわかりません。
何卒ご教示お願いいたします。
a = [1,4,5,2,3,6]
b = [1,4,3]
I = [-1] * len(b)
last = 0
for i,n in ...
3
票
2
回答
977
閲覧数
重み付きレーベンシュタイン距離の定義について
文字列間の距離を測るレーベンシュタイン距離の拡張の重み付きレーベンシュタイン距離というものの定義がよく分からなくなったので質問します。
通常のレーベンシュタイン距離は、文字列1を文字列2に編集する場合の挿入・削除・置換の最少回数を距離としています。挿入・削除・置換についてそれぞれ重みを設定して合算するのが重み付きレーベンシュタイン距離だそうです。
http://id.fnshr.info/...
1
票
0
回答
738
閲覧数
BPE (Byte Pair Encoding、バイト対符号化)の効率のいい実装について
お世話になっています。さて厳密にはBPEではないと思いますが、類似のアイディアを文字列に適用したものがあります。
辞書に3つの単語があるとします(本番はもっと巨大な辞書を使います)
我
喜欢
水果
そして次の入力を取ります。
我喜欢水果
これを1文字ずつに分解します。
我 喜 欢 水 果
隣り合う2つの文字を連結して辞書引きをします。
我喜
喜欢 <- in the dic
...
1
票
3
回答
438
閲覧数
プログラミングCの再帰に関しての質問です。
Cの初心者です。
再帰を使用して、ユーザーが入力した自然数(入力される自然数の数は分からない)をscanfで読み取り、その中から最大値を返す関数int max()を書くという課題です。ユーザーが入力する最後の自然数は0でなくてはならず、0が入力されたら関数は必ず終了し、その時点での最大値を返す。
配列やリスト、ループを使わずに再帰だけで書かなければならず、...