[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
273
質問
0
票
2回答
429 件の閲覧数
深さ優先探索と幅優先探索の入力と使い方について
スタックを使った「深さ優先探索」とキューを使った「幅優先探索」について、入力と使い方に関してわからないことが2点あります。
現在のコードを実行するときは、2分探索木(以下の例)を入力としていますが、深さ優先探索と幅優先探索の入力は2分探索木でなければならないのでしょうか。
T = ((((), 111, ()), 11, ((), 112, ())), 1, (((), 121, ()), ...
0
票
1回答
179 件の閲覧数
コーディングテスト問題「FrogRiverOne」について
コーディングテスト練習サイトCodilityの「FrogRiverOne」という問題について、問題の理解とコードがなぜあるケースでincorrectになるのかわからず困っています。
FrogRiverOne coding task - Learn to Code - Codility
上記のFrogRiverOneについて日本語で書かれた記事
以下問題文を原文引用しました。...
0
票
2回答
404 件の閲覧数
数列を許容範囲でグループ化(分割)する方法を教えて下さい。
例
input 数列 {1, 2, 2.01, 3} と 許容誤差(範囲)=0.1
output {1} {2, 2.01} {3}
①タイトルで意味が通じますか?正式名称があれば教えて下さい。検索語が思いつきませんでした。
②outputを、区切り1.5と2.5(2.8でも可)にする予定です。
③特に言語にこだわりません。おすすめのページがあれば教えて下さい。
よろしくお願いします。
...
0
票
1回答
2,387 件の閲覧数
ポインタの値をバブルソートで並べ替えたい
C言語でポインタで定義した値を昇順に並べ替えたいので,バブルソートの関数を作成しています.
現状では,下記の関数を作成しましたが,ポインタの書き換えができていないためか元の値とは関係ない数値(0.00,-737.05,67662660000000000.00など)が出力されます.
やりたいことは「一つのポインタで定義している全ての値を昇順に並べ替える」ということなので,
...
0
票
2回答
7,517 件の閲覧数
C#でスレッドセーフなシングルトンクラスを実装したい
タイトルの件、WCFサービス上でシングルトンクラスを扱うことを想定してスレッドセーフな
実装をしたいと考えております。
検索もしてみたのですが、いくつか方法があるようで実際どれが正しいのか
よく分かりません。。
大変恐縮ですが、サンプルコード等のリンクでも構いませんので、
ご教示頂けないでしょうか?
0
票
2回答
2万 件の閲覧数
C# App.configのデータ取得について
C#のApp.configについての質問です。
アプリを立ち上げたときに、App.configからドロップダウンリスト1のデータおよび、その他のドロップダウンリスト2のデータを読み取りたいと思っています。また、keyとそのvalueは後に使用するので、まだ実装していませんが、App.configから読み込むときに、配列もしくはリストに格納しようと考えています。
App....
0
票
1回答
71 件の閲覧数
有向グラフの表現で、E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} の表すものが分からない
有向グラフG=(V,E)の時、V = {1, 3, 4, 5, 6, 12} and E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} といった表現がされていた場合のEの右辺の表現が理解できません。この場合はどのようなグラフが期待されるのでしょうか?ご教示いただけると幸いです。
0
票
1回答
212 件の閲覧数
値を中心として, 前後にある数だけ幅を取るために使用できるアルゴリズムがありますか
値を中心として, 前後にある数だけ幅を取るために使用できるアルゴリズムがありますか
例えばこの入力で平均値99を基準に, 幅を15とすると
98
174
58
49
78
90
75
170
下のような結果を期待しています.
36-51
52-67
68-83
84-99
100-115
116-131
132-147
148-163
164-179
これは平均値を求め, ...
0
票
2回答
299 件の閲覧数
python 配車問題
pythonを最近学習し始めた者です。
pythonを使用してやりたいことがあるのですが、キーワードがわからない為、やり方を検索できずにいます。
以下やりたい内容となります。
やりたいこと:ある地域の中に3つのタクシー会社があるとします。(会社A・会社B・会社C)各会社の所有タクシー数は、[会社A:2台][会社B:2台][会社C:1台]
タクシーを呼ぶ人は地域内の建物にいることとし、...
0
票
1回答
73 件の閲覧数
ヒープの深さと各深さにおける要素数から和を求めるプログラムのエラー
前回の質問
要素数nのヒープの深さと各深さにおける要素数を求める方法について
でいただいたコメントを参考に以下のプログラムを書き、実行しましたがエラーが出ています。
エラー
$ python sample.py
depth_list
[0, 1, 2, 3]
element
[1, 2, 4, 1]
Traceback (most recent call last):
File "...
0
票
2回答
154 件の閲覧数
コーディングテストにおけるコードのTIMEOUT ERRORについて
オンラインでコーディングテスト練習ができるCodilityのMaxProductOfThreeという問題のコードですが、テストケースが全て正解でもDetected time complexityがO(N**3)だったので、テストスコアが44%/100%と表示されました。
(参考)MaxProductOfThreeについて日本語で書かれた記事
参考記事で書かれているO(N)...
0
票
2回答
168 件の閲覧数
コードのパフォーマンスについて
コーディングテスト練習サイトCodilityの「FrogRiverOne」という問題で、書いたコードのパフォーマンスが悪かったのですが、どのように改善すれば良いのでしょうか。
パフォーマンスの良いコードの書き方がよくわかっていないので、学べるサイトや教材などももしおすすめのものがあれば教えていただきたいです。
FrogRiverOne coding task - Learn to Code - ...
0
票
1回答
163 件の閲覧数
アットコーダーの問題について(Colorful Subsequence)
下記アットコーダーの問題がわかりません。
https://atcoder.jp/contests/agc031/tasks/agc031_a
解説やACの方のコードを見てみましたが26サイズのint配列にc[各文字 - 'a']++を
し、A.答え *= c[i]を繰り返すと求めるべき出力になるのか理解できませんでした。
噛み砕いて解説いただけると幸いです。
ーー
問題文
長さ Nの文字列 ...
0
票
3回答
1,826 件の閲覧数
幅優先探索を、キューを使わずに再帰関数を使って実装することはできるのでしょうか?
質問
グラフ構造に対して幅優先探索を再帰関数を使って実装することはできるのでしょうか?
深さ優先探索の場合、スタックか再帰関数を使って実装ができます。
一方で深さ優先探索の場合、キューを使って実装することはできたのですが、キューを使わずに再帰関数で実装することができずに困っています。
参考までに、キューを使った実装を下にのせておきました。幅優先探索するためのヒントもしくは、...
0
票
1回答
497 件の閲覧数
lzwの圧縮、解凍について
お世話になります。
今回、初めてGIFファイルの勉強をしようと、lzwの圧縮、解凍をC#で組んでみたのですが、
どうもうまくいきません。
圧縮まではうまくいっているようなのですが、解凍しようとすると、余計なところに『0』が
入ってしまい、正しく解凍されません。
ほかサイト様など、さまざまなところを拝見させていただいているのですが、どうも
原因がわかりません。
...
0
票
2回答
764 件の閲覧数
異なる文字数の、文字列類似度の算出方法は?
下記が50%だとすると、
天下
天一
下記は類似度何%になるでしょうか?
・一致数4 ÷ 全文字数22 × 100 = 22%でしょうか?
・また、この場合、「天下」から見た「天下一武道会へ出場してみたいけど」も、「天下一武道会へ出場してみたいけど」から見た「天下」の類似度も同じ?
天下
天下一武道会へ出場してみたいけど
その他、どんな「算出方法」や「考え方」...
0
票
1回答
466 件の閲覧数
論文などに書かれているアルゴリズムをC/C++に変換するトランスレータはありませんか
論文に書かれているALGOLのような擬似コードを見るのですが、それを外形だけでもCやC++にしたいのですが、自分で打ち込むよりも手っ取り早く変換することができればより多くの論文を実行して読めると思いました。
擬似コードやALGOLをC/C++へ変換できるトランスレータはありませんか
FORTRANをCに変換するソフトウェアは有名ですがALGOLや擬似言語については見当たりませんでした。
0
票
1回答
64 件の閲覧数
AtCoder Beginner Contest 180 Takahashi Unevolved D問題
D - Takahashi Unevolved 解説リンク
https://atcoder.jp/contests/abc180/editorial/219
上記リンク先に掲載されている解答コードで
ans+(y-1-x)//b
の部分がありますが、ここで-1をする理由がわかりませんでした。
こちらの意味を教えていただけないでしょうか。
よろしくお願いします
0
票
1回答
121 件の閲覧数
平方数の判定を、sympyの素因数分解factorintでできますか?
目的は、平方数の判定を一行でできますか?よろしくお願いします。
print(factorint(9))
{3: 2}
print(factorint(81))
{3: 4}
参考nが平方数かどうか調べる時
https://teratail.com/questions/200122
参考:Wolfram|Alpha
81は平方数ですか
https://ja.wolframalpha.com/...
0
票
1回答
117 件の閲覧数
多角形同士の衝突判定のアルゴリズムについて
多角形同士の衝突判定のアルゴリズムを検討しています。
愚直に衝突判定を行う場合、多角形の各直線が別の多角形と衝突していないか、全直線同士組み合わせでチェックしていくのかと思います。
ただし、この方法だと多角形の頂点数が多い場合や、多角形が多い場合に処理が非常に多くなってしまうと思われます。(多少は処理を間引きできるとは思いますが)
高速で衝突判定ができるようなアルゴリズムはあるでしょうか?
0
票
1回答
129 件の閲覧数
Pythonでの単方向リストの実装
Pythonを用いてリストを実装しようとしています。
Linked List のようにして実装しています。
以下のコードの「ここ!!」とした部分ですが、なぜreturnする必要があるのでしょうか。self.headにnew_nodeが入ってif文は終わりなのではないでしょうか。
試しにreturnを消してみると、プログラムが止まらず、同関数内のwhileから抜けられていないことがわかりました。
...
0
票
1回答
89 件の閲覧数
Outlineビューを実現したいが、木構造を一次元のリストで表現できるような構造の名前を知りたい
概要
タイトル通り、実現したい構造があるのですが、いまいち具体的に言語化もできず、どのようにアプローチしたら良いのか分からず困っているので、以下の要件を実現できる構造をご存知であれば教えていただけると非常に助かります。
テーブルに木構造を表示するために、データを一次元配列で提供できる
その際、Orderを保持できる(画像のイメージ)
定数時間での検索が可能O(1)
AppendToParent, ...
0
票
1回答
116 件の閲覧数
クイックソートのpivotが中央値が最も良いとされる理由
クイックソートのpivotが中央値が最もいいとされる理由の認識は下記の通りであっていますでしょうか
以下のような配列があった場合、下のようにpivotに中央値を選び均等に分割できたとします。次にグループAで同じ処理を繰り返すとき、Bの要素は無視してAの中の要素とだけ比較すればよい。Bの要素を無視するので比較回数・交換回数が大幅に減る。Bも同様
よって中央値で分割できると高速で処理できる。
[4,3,...
0
票
1回答
94 件の閲覧数
二分探索木を分割する際の計算量
https://www.geeksforgeeks.org/split-a-bst-into-two-balanced-bsts-based-on-a-value-k/?ref=leftbar-rightbar
こちらのコードを用いてBSTを分割する際の計算量は、O(h)(hはツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。...
0
票
1回答
167 件の閲覧数
c++でのスタック構造について
逆ポーランドを実装しようとした際に、 while(scanf("%s", s) != EOF) で入力を受け取った後に if(s[0] == '+') で条件分岐が始まるのですが、なぜ s[0] と配列 s のインデックスを 0 に固定したままでも良いのでしょうか?
s[0] の次は s[1] 、さらに s[2] とインデックスを増やしていき、最終的に s[n] が EOF ...
0
票
3回答
183 件の閲覧数
異なる文字列の接頭語と接尾語を比較
ある文字列S1、S2があるとして、S1の接尾語はS2の接頭語を反転させたものと等しいか比較し、一致する箇所だけをS2から削除したのち、その2つの文字列を連結させるというプログラムを実装したいのですが、効率的な方法はありますでしょうか。
現在は、
S1,S2を読み込む
S1を反転
S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。
...
0
票
1回答
263 件の閲覧数
プログラムの実行時間をできるだけ短くしたい
プログラムの実行時間をできるだけ短くしたいです。
最終的なゴールは、入力Nを読み込み、評価して2つの連結リストにそれぞれ結果をストアし、その結果を順に出力することです
入力の条件は、
The first line contains the integer N. The second line contains N integers, a0,a1,...,aN−1. The integers ...
0
票
1回答
211 件の閲覧数
一つのプログラムで複数の連結リストの作成
配列を使わず、連結リスト(単方向)のみでキューのデータ構造を実装したいです。 C言語を用いて、一つのプログラムで複数の連結リストを実装することは可能でしょうか?structの定義で行き詰まってしまったので、実例も教えてくださると嬉しいです…。
追記
struct node1
{
int data1;
struct node1 *next1;
};
struct node2
...
0
票
1回答
247 件の閲覧数
LeetCodeでBrute ForceするとTime Limit Exceededする
LeetCodeをはじめました。
さっそくですが、Two sumでエラーがでたので教えてほしいです。
まず、Brute Forceで下記コードを書きました。
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type ...
0
票
1回答
390 件の閲覧数
Pythonでの迷路の問題が解けません
問題の本文はこちら: AtCoder Typical Contest 001 A - 深さ優先探索
自分のコードは以下の通りです。
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
maze = [list(map(str, input().split())) for _ in range(H)]
...
0
票
1回答
401 件の閲覧数
ベクトルが与えられた時にノルムを求めるアルゴリズムについて
前提
ベクトル(v = (v1, v2, ...vn)^T))が与えられた時にノルム(√(v^(T)v))を求めるアルゴリズムを考えて、c言語で実装しようとしています。
実現したいこと
①擬似コードで文章になっている部分をどのように記号で表せるのか知りたい
②擬似コードのアルゴリズムを実行するためには、どのように参考記事のプログラムを変更するべきか知りたい
...
0
票
2回答
671 件の閲覧数
ダイクストラ法の実装
ダイクストラ法をmain関数内の「課題追加部分」で実装するのですが方法がわかりません...
実装方法を見ても①から意味がわからない状態です...
import java.util.*;
public class Dijkstra {
public static void main(String[] args) {
final List<LocatedVertex&...
0
票
1回答
144 件の閲覧数
動的計画法でナップサック問題を解く
動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。
なぜでしょうか?
1から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。
多くの解説ではdpテーブルの遷移を
dp[i][p]: i-1 番目までの品物から重さが p を超えないように選んだときの、価値の総和の最大値
としていますが、これを
i番目(i-...
0
票
2回答
109 件の閲覧数
キューを使った双方向リストに関するプロセス処理
Aizu Online JudgeのALDS1_3_Cの問題を解いています。
双方向連結リスト | アルゴリズムとデータ構造 | Aizu Online Judge
原因不明のエラーに悩んでいます。以下がソースコードになります。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#...
0
票
1回答
298 件の閲覧数
C++で2進数文字列を10進数文字列に直接変換したい
現在、c++で多倍長整数クラスBigIntを作成しているのですが、toString()の実装に行き詰まっています。数値を2進数文字列に変換するのはできましたが、それを更に10進数文字列に変換する方法がわかりません。
2進数文字列を10進数文字列に直接変換する方法がありましたらご教授ください。
0
票
1回答
204 件の閲覧数
LeetCodeにおける入出力について
コーディング問題サイトLeetCodeのAddBinary
という問題を解き、ローカル環境ではテストケースの正しい答えを得ることができたのですが、LeetCodeのWebサイトで実行(Run Codeボタンをクリック)すると以下のエラーが起きてしまいます。
LeetCodeに合わせた入出力条件にするためには、コードをどのように改変するべきでしょうか。
実行したコード
class ...
0
票
1回答
131 件の閲覧数
コーディングテスト問題「Triangle」について
コーディングテスト練習サイトCodilityの「Triangle」という問題について、
問題の理解とコードがなぜあるケースでincorrectになるのかわからず困っています。
Triangle coding task -Learn to Code - Codility
上記の問題について日本語で解説された記事
テストケースについて以下の注意が表示されましたが、
...
0
票
1回答
91 件の閲覧数
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 (...
0
票
1回答
187 件の閲覧数
KMP法が分からないので調べているのですが
リンク先下表について
Q1
・「abbabbababに対するシフト幅」とはどういう意味ですか?
・「検索テキスト」と「パターン」を比較しているわけではなく、事前の「パターン」同士の比較テーブルを作成する時の話?
・「abbabbabab」はパターンのこと??
Q2
・備考欄に「一致なし」と記載されていますが、どういう意味?
・「何」と「何」が一致していないのでしょうか?
0
票
2回答
310 件の閲覧数
データベースから取得したオブジェクト同士の親子関係をハッシュで表現したい
実現したいこと
D3.js のTreeView(以下画像のような)に利用するjsonを、Ruby on Railsアプリケーションのデータベースから動的に作成したい。
具体的には、
Item(name:string, parent: string) # ただし、parentは、ツリービューにおける親の名前を指す)
のようなItemモデルのオブジェクトが多数@itemsとしてあり、
...
0
票
1回答
278 件の閲覧数
rubyで書いた二分探索の再帰コードを評価お願いします
バイナリーサーチ/二分探索のコードを再帰を使ってRubyで自分なりに、実装してみました。
採点というか評価していただけないでしょうか? 正しく動くのですが、書き方としてどうなのかが心配でした。
※bubble_sort(list)で昇順ソートすると仮定してください。
def binary_search(list,target)
sorted_list = bubble_sort(list)
...
0
票
1回答
711 件の閲覧数
python3で深さ優先探索の再帰関数が上手く機能しない
こんにちは。python3で作ったこちらの再帰関数が上手く機能しません。
def func(teleports_string):
strings = [{n[0],n[1]} for n in teleports_string.split(',')]
start = {'1'}
def search(strings,point,...
0
票
2回答
248 件の閲覧数
いい試合順にランク付けするアルゴリズム
スポーツ等の複数の試合をリアルタイムにいい試合順にランク付けするプログラムを作成しています。
いい試合の基準として、時間が大きくかつ点差が小さいものがいい試合だと考えれれます。
つまり、x軸を時間y軸を点差とした時に、試合の1時的な情報の集合を取得し、時間、点差を正規化し、グラフを描画した時に右下にある試合がいい試合(時間が経過しているのに点差が開いていない)ということになり、左上にある試合(...
0
票
1回答
223 件の閲覧数
同じ数同士左から順に線で結んだとき、交点ができるか否かの判定について
昨日質問した
同じ数同士線で結んだとき、交点ができるか否かの判定について
の一般化を考えてみました。
ary1 = [1, 1, 2, 3, 3, 3, 2, 2, 1]
を考えることにします。
1と1を左から順番に飛ばさず上側で結びます。
同様に2と2を、3と3を飛ばさず上側で結びます。
(無理やり結んだ曲線を交差させないかぎり)
交点は0個です。
一方
ary2 = [1, 1, 3, 2,...
0
票
2回答
1,265 件の閲覧数
レーベンシュタイン距離は、「置換に割り振るコストの値」によって結果が異なる?
「kitten」「sitting」、2単語間のレーベンシュタイン距離は、設定によって「3」だったり「5」だったりするのでしょうか?
・「レーベンシュタイン距離」はあくまでも考え方であって、正式な公式は存在しない?
・あるいは、公式はあるけれども、そこへ割り振るコストは自由に設定可能ということでしょうか?
・一般的には置換コストは「1」「2」、何れなのでしょうか?
上の変形では挿入・削除・...
0
票
1回答
222 件の閲覧数
0
票
1回答
134 件の閲覧数
三角波を用いた変換に名前はあるのですか?
フーリエ変換のプログラムに矩形波を用いたものをウォルシュ・アダマール変換と呼びますが、三角波を用いても変換ができると考えました。この三角波を用いたものにすでに名前はあるのですか?
0
票
1回答
57 件の閲覧数
エラー: 'closure' 型のオブジェクトは部分代入可能ではありません
Bootstrap法によって機械学習アルゴリズムの精度を検証するプログラムを作っています。
以下のコードをテキストで作成し、CSVdataをread.csvで読み込んで、以下のように実行すると
> source("text.txt")
> exdata=read.csv("final_output.csv",header=TRUE)
> ...
0
票
0回答
77 件の閲覧数
Atcoder abc165_c 期待する答えが出力されません
以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。
方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。
Atcoder abc165_c
問題概要
Q ...
0
票
0回答
87 件の閲覧数
平叙文(穴埋め問題)から疑問文(一問一答問題)を作成したい
教科書の文から作った穴埋め問題を一問一答形式の問題にしたいです。
例)(文)メフメト2世はビザンツ帝国を滅ぼした (空所単語)ビザンツ帝国
→(問)メフメト2世が滅ぼしたのはどこ。(答)ビザンツ帝国
現実的に可能かどうか教えてください。
以下のような手順で作成しようと思っています。
品詞分解(形態素解析)
↓
単文・複文・重文の判別(主語述語の個数、並べ方から判別。...