すべての質問
35 件の質問
6
票
1
回答
1,162
閲覧数
C++での自己参照構造体におけるポインタにおいて
C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照)
この場合、p,l,rの型はNodeではなくてNode*です。
これはNodeではいけないのでしょうか?
ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、
ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。
struct Node {
int key;
...
5
票
0
回答
158
閲覧数
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?
グラフ構造、たとえばツリー構造を探索することを考えます。
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。
この時、
幅優先探索はしばしばキューを用いて
深さ優先探索はしばしばスタックを用いて
それぞれ実装されます。
これはちょうど、
各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う
次のノードを pop() ...
4
票
3
回答
1,595
閲覧数
逆ポーランド記法で被演算子が3個以上の演算はありうるのか?
中間記法「3 + 4」は逆ポーランド記法だと「3 4 +」のように書けます。
では、被演算子が3個以上、たとえば中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか?
「3 4 + 5 + 」と書けばよさそうですが、「3 4 5 +」のように書くことはできないのでしょうか?
(乗算でも同様にできそうですが引き算だとどうなるのかちょっとよくわからないですね)
4
票
1
回答
145
閲覧数
ruby で ordered hash 的なことがやりたい
ruby で、木構造で実装される Map データ構造が扱いたくなりました。以下の条件を満たすクラスはありますか?ないし、実装したライブラリなどはありますか?
h.set(key, value) で値を store でき、 h.get(key) にてそれを取得できる。それらは O(log(N)) 以下で実行できる
h.find_sup(key) にて、 key よりも大きな最小のキーと、...
4
票
1
回答
804
閲覧数
グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい
グラフ理論に関する質問です。
頂点(ノード)間の位置関係をinvariantに保持する方法・表現を考えたいです。
具体的な例として、ある化合物の分子を考えます。
ここで、その分子内の原子(グラフにおける頂点)たちと、
各原子の三次元座標(3次元ベクトル)が与えられています。
この三次元座標を用いて、頂点間の距離(グラフにおける辺の長さ)などが計算できます。
ここで、化合物内のある原子(...
3
票
2
回答
1,429
閲覧数
Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス
次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、
実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。
もし可能であればそれらの判定方法の計算量も教えてもらいたいです。
おそらくO(1)であって、O(N)まではいかないにしてもわずかながら差があるのだろうなと思っています。
...
3
票
1
回答
294
閲覧数
帰りがけ順から二分探索木の生成
ネットでは、行きがけ順・通りがけ順、通りがけ順・帰りがけ順からBSTを生成する方法はよく見かけますが、帰りがけ順のみ与えられた場合、そこから探索二分木を生成することは可能なのでしょうか?また、その場合どういったアルゴリズムになりますか?
3
票
1
回答
188
閲覧数
gurobi からpyomoへの変換
pythonでgurobiからpyomoへ二次制約付き問題であるため、変更したいのですがやり方がわからなくて困っています。
from gurobipy import *
import pandas as pd
import numpy as np
import csv
from pyomo.environ import SolverFactory
opt = SolverFactory("...
2
票
1
回答
333
閲覧数
ハッシュ表のチェイン法による実装における単方向or双方向連結リストの比較
ハッシュ表のチェインほうで双方向リストのほうが優れている点はありますでしょうか?
有名な教科書のMIT教科書アルゴリズムイントロダクション第3版のP213の図11.3の解説文。
ハッシュ表をチェイン法で実装してる解説で疑問点があったので質問します。
「連結リストは一方向、あるいは双方向であり、図は削除が高速にできる双方向連結リストである」という記述があります。
...
1
票
1
回答
453
閲覧数
レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して
レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。
以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。
「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(...
1
票
2
回答
173
閲覧数
ZIPコンテナを効率よく読み込むには?
通信用語の基礎知識さんのZIPコンテナの記事を見て、自分でZIPコンテナファイルの実装を作ろうと考えているのですが、ZIPファイルを解凍せずにZIPファイルの中身を読み込んだり書き込んだりするにはどうすればいいのでしょうか?
(ZIPコンテナというのはePubで使われている規格です。)
...
1
票
2
回答
205
閲覧数
1次元配列を木構造の形に成形したい
自身のIDと親IDを持つOriginalDataを木構造の形にしたいと考えています。
inputDatasをresultの形に変換したい
再帰的な処理をしたいのですが、いい方法が思いつきません。
言語は特に何でも大丈夫です。
struct OriginalData {
let id: String
let parentID: String?
}
struct Node {
let ...
1
票
2
回答
533
閲覧数
計数ソートを入力順にソートした際の安定性
下の疑似コードで実装された計数ソート(Counting Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか?
事実、このアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。
私は。同じ要素が複数回出現した場合に限り、その要素数-...
1
票
0
回答
272
閲覧数
バケツソートの最低ケースを改善するためには
バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか?
教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
0
票
1
回答
1,431
閲覧数
データ構造とアルゴリズムは実務ではどんなシーンで役立つのか? [クローズ済み]
現在スタック、キュー、ツリー、ソートなどを始めとしたデータ構造とアルゴリズムの勉強をしています。これはエンジニアの基礎的なスキルだから(と世間様が言ってる)という理由が私のモチベーションです。
ですがここで質問です。
質問
これらが重要と認識されてる方は、これまでご自身の開発でどのようなシーンで使ってきたか教えてもらいたいです。もしできれば、...
0
票
3
回答
1,030
閲覧数
ヒープデータ構造について
n 個の要素を持つヒープの、高さ h における節点が n/2^(h+1) 個である、理由がわかりません。
問題文の原文はこちらです:
Show that there are at most ⌈n/2^(h+1)⌉ nodes of height h in any n-element heap.
以下がIntroduction to Algorithms 練習問題6.3-...
0
票
1
回答
572
閲覧数
Judy arrayとは何ですか?
連想配列のようですが
連想配列ならmapやすでにSTLで用意されているで十分に足りると思うのですが
なぜ、Judy arrayというものが生まれたのですか
mapやsetと比べてそちらで用意されているものは何が大きく違うのですか?
0
票
2
回答
534
閲覧数
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される
ダイクストラ法のコード(python)を参考に以下のプログラムを実行しました。
出力として最短ルートは'A->C->B->D'と求められましたが、コストは「5+(-4)+1=2」になるところ、'A->B->D'の「3+1=4」が出力されました。原因がわからないです。
グラフ部分はコードのrouteにあたります。
出力
$ python dijkstra.py
visited to A.
...
0
票
1
回答
187
閲覧数
データ構造のヒープへの挿入方法について
データ構造のヒープへの挿入方法で質問です。
ヒープへの挿入は、今あるノードの末尾に新しいノードを追加し、
その後、ヒープの条件を満たすような修正のオペレーションをすることだと
書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で見ました。
ネットでしらべても同様でした。
また挿入の計算量はlogH (Hは完全二分木の高さ)だとも見ました。
ここで疑問です。
...
0
票
1
回答
154
閲覧数
文字列結合した際に、文字Kが文字aを消してしまう
現在、leetcodeの1768. Merge Strings Alternatelyを解いています。
下記が問題文(*1)と例題(*2)です
事象は、文字列結合した際に、文字Kが文字aを消してしまうことです。
コードは'(*3)にあります。
この原因と改善方法について教えていただけると幸いです。
*1
2 つの文字列 word1 と word2 が与えられます。 word1 ...
0
票
1
回答
242
閲覧数
クイックソートのパーティションの定義について
現在、ALDS1_6_B を行っています。
解答コードは、以下のようになります。
その中で、パーティションの中で使われているint i = p-1の意味がわかりません。
なぜ、iは、p-1を行っているのでしょうか? どういう理由で、p-1を定義しているのでしょうか?
また xを閾値として、for文の中で比較して、x未満とx以上を分けていると思うのですが、
なぜiを使うことで、...
0
票
1
回答
92
閲覧数
有向グラフの表現で、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
回答
58
閲覧数
51. Reverse Words in a String : Inputが"the sky is blue"のとき、"blue is is blue "と出力されてしまう。(期待結果:"blue is sky the")
現在、leetcodeの151. Reverse Words in a Stringを解いています。
下記に問題文(*1)と例(*2)、コード(*3)を載せています。
事象としては、与えられた文字列が"the sky is blue"のとき、"blue is is blue "と出力されてしまいます。
期待結果は"blue is sky the&...
0
票
1
回答
162
閲覧数
2種類のポインタを用いた線形リストの中央の要素の発見の仕方
長さが未知の線形リストの中央の要素はどのようにして見つければよいかという問題について、講義内で速いポインタと遅いポインタの2種類を使うことで見つけることが出来るという説明を講義内で受けたのですが、この速いポインタ、遅いポインタという概念について、解説がされている本やWebページなどがありましたら教えていただきたいです。
0
票
1
回答
176
閲覧数
ダブルハッシュを使用したオープンアドレス法について
現在、AIZU ONLINE JUDEGE ALDS1_4_Cをやっています。
その中で、ダブルハッシュを使用したオープンアドレス法を学んでいます。
以下がオープンアドレス法のコードです。
#include <stdio.h>
#include <string.h>
using namespace std;
using ll =long long;
#define M ...
0
票
1
回答
218
閲覧数
Outlineビューを実現したいが、木構造を一次元のリストで表現できるような構造の名前を知りたい
概要
タイトル通り、実現したい構造があるのですが、いまいち具体的に言語化もできず、どのようにアプローチしたら良いのか分からず困っているので、以下の要件を実現できる構造をご存知であれば教えていただけると非常に助かります。
テーブルに木構造を表示するために、データを一次元配列で提供できる
その際、Orderを保持できる(画像のイメージ)
定数時間での検索が可能O(1)
AppendToParent, ...
0
票
1
回答
171
閲覧数
二分探索木を分割する際の計算量
https://www.geeksforgeeks.org/split-a-bst-into-two-balanced-bsts-based-on-a-value-k/?ref=leftbar-rightbar
こちらのコードを用いてBSTを分割する際の計算量は、O(h)(hはツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。...
0
票
3
回答
314
閲覧数
異なる文字列の接頭語と接尾語を比較
ある文字列S1、S2があるとして、S1の接尾語はS2の接頭語を反転させたものと等しいか比較し、一致する箇所だけをS2から削除したのち、その2つの文字列を連結させるというプログラムを実装したいのですが、効率的な方法はありますでしょうか。
現在は、
S1,S2を読み込む
S1を反転
S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。
...
0
票
1
回答
738
閲覧数
一つのプログラムで複数の連結リストの作成
配列を使わず、連結リスト(単方向)のみでキューのデータ構造を実装したいです。 C言語を用いて、一つのプログラムで複数の連結リストを実装することは可能でしょうか?structの定義で行き詰まってしまったので、実例も教えてくださると嬉しいです…。
追記
struct node1
{
int data1;
struct node1 *next1;
};
struct node2
...
0
票
1
回答
100
閲覧数
ヒープの深さと各深さにおける要素数から和を求めるプログラムのエラー
前回の質問
要素数nのヒープの深さと各深さにおける要素数を求める方法について
でいただいたコメントを参考に以下のプログラムを書き、実行しましたがエラーが出ています。
エラー
$ python sample.py
depth_list
[0, 1, 2, 3]
element
[1, 2, 4, 1]
Traceback (most recent call last):
File "...
0
票
1
回答
184
閲覧数
動的計画法でナップサック問題を解く
動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。
なぜでしょうか?
1から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。
多くの解説ではdpテーブルの遷移を
dp[i][p]: i-1 番目までの品物から重さが p を超えないように選んだときの、価値の総和の最大値
としていますが、これを
i番目(i-...
0
票
2
回答
720
閲覧数
深さ優先探索と幅優先探索の入力と使い方について
スタックを使った「深さ優先探索」とキューを使った「幅優先探索」について、入力と使い方に関してわからないことが2点あります。
現在のコードを実行するときは、2分探索木(以下の例)を入力としていますが、深さ優先探索と幅優先探索の入力は2分探索木でなければならないのでしょうか。
T = ((((), 111, ()), 11, ((), 112, ())), 1, (((), 121, ()), ...
0
票
1
回答
297
閲覧数
Pythonにおける変数の値参照について質問です
LeetCodeのアルゴリズム第83問について質問です。
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
以下問題文と入力,出力例です。
Given the head of a sorted linked list, delete all duplicates such that each element ...
0
票
1
回答
330
閲覧数
二次元配列に条件付きで数字を代入
与えられた数字を二次元で保存したいです。例えば、数列{3,12,4,1,5,8}を与えられたとして、一番目の数字3を配列1に挿入、二番目の数字12は、3より大きいので別の配列2に挿入、左から走査し、4は12より小さいので配列2に挿入、1は左から走査し3より小さいので配列1に挿入...ということを行いたいです。
構造的には、二次元リスト
int s = {3,12,4,1,5,8}
int ...
0
票
2
回答
119
閲覧数
2つのいくつかのノードを共有する連結リストをソートしたい
最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?
たとえば
-900->120->200->230
\
452->700
/
-10->200
...