Skip to main content

すべての質問

でタグ付けされた
絞り込み
並べ替え
タグ付けされた
6
1 回答
1,162 閲覧数

C++での自己参照構造体におけるポインタにおいて

C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照) この場合、p,l,rの型はNodeではなくてNode*です。 これはNodeではいけないのでしょうか? ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、 ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。 struct Node { int key; ...
Haruna Ojima's user avatar
5
0 回答
158 閲覧数

グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?

グラフ構造、たとえばツリー構造を探索することを考えます。 ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。 この時、 幅優先探索はしばしばキューを用いて 深さ優先探索はしばしばスタックを用いて それぞれ実装されます。 これはちょうど、 各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う 次のノードを pop() ...
rugamaga's user avatar
  • 915
4
3 回答
1,595 閲覧数

逆ポーランド記法で被演算子が3個以上の演算はありうるのか?

中間記法「3 + 4」は逆ポーランド記法だと「3 4 +」のように書けます。 では、被演算子が3個以上、たとえば中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか? 「3 4 + 5 + 」と書けばよさそうですが、「3 4 5 +」のように書くことはできないのでしょうか? (乗算でも同様にできそうですが引き算だとどうなるのかちょっとよくわからないですね)
Akiyama Nao's user avatar
4
1 回答
145 閲覧数

ruby で ordered hash 的なことがやりたい

ruby で、木構造で実装される Map データ構造が扱いたくなりました。以下の条件を満たすクラスはありますか?ないし、実装したライブラリなどはありますか? h.set(key, value) で値を store でき、 h.get(key) にてそれを取得できる。それらは O(log(N)) 以下で実行できる h.find_sup(key) にて、 key よりも大きな最小のキーと、...
Yuki Inoue's user avatar
  • 1.7万
4
1 回答
804 閲覧数

グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい

グラフ理論に関する質問です。 頂点(ノード)間の位置関係をinvariantに保持する方法・表現を考えたいです。 具体的な例として、ある化合物の分子を考えます。 ここで、その分子内の原子(グラフにおける頂点)たちと、 各原子の三次元座標(3次元ベクトル)が与えられています。 この三次元座標を用いて、頂点間の距離(グラフにおける辺の長さ)などが計算できます。 ここで、化合物内のある原子(...
neco's user avatar
  • 91
3
2 回答
1,429 閲覧数

Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス

次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、 実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。 もし可能であればそれらの判定方法の計算量も教えてもらいたいです。 おそらくO(1)であって、O(N)まではいかないにしてもわずかながら差があるのだろうなと思っています。 ...
Akiyama Nao's user avatar
3
1 回答
294 閲覧数

帰りがけ順から二分探索木の生成

ネットでは、行きがけ順・通りがけ順、通りがけ順・帰りがけ順からBSTを生成する方法はよく見かけますが、帰りがけ順のみ与えられた場合、そこから探索二分木を生成することは可能なのでしょうか?また、その場合どういったアルゴリズムになりますか?
Avril's user avatar
  • 117
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("...
炎天下修羅's user avatar
2
1 回答
333 閲覧数

ハッシュ表のチェイン法による実装における単方向or双方向連結リストの比較

ハッシュ表のチェインほうで双方向リストのほうが優れている点はありますでしょうか? 有名な教科書のMIT教科書アルゴリズムイントロダクション第3版のP213の図11.3の解説文。 ハッシュ表をチェイン法で実装してる解説で疑問点があったので質問します。 「連結リストは一方向、あるいは双方向であり、図は削除が高速にできる双方向連結リストである」という記述があります。 ...
Akiyama Nao's user avatar
1
1 回答
453 閲覧数

レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して

レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。 以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。 「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(...
user avatar
1
2 回答
173 閲覧数

ZIPコンテナを効率よく読み込むには?

通信用語の基礎知識さんのZIPコンテナの記事を見て、自分でZIPコンテナファイルの実装を作ろうと考えているのですが、ZIPファイルを解凍せずにZIPファイルの中身を読み込んだり書き込んだりするにはどうすればいいのでしょうか? (ZIPコンテナというのはePubで使われている規格です。) ...
Nagkei10's user avatar
  • 233
1
2 回答
205 閲覧数

1次元配列を木構造の形に成形したい

自身のIDと親IDを持つOriginalDataを木構造の形にしたいと考えています。 inputDatasをresultの形に変換したい 再帰的な処理をしたいのですが、いい方法が思いつきません。 言語は特に何でも大丈夫です。 struct OriginalData { let id: String let parentID: String? } struct Node { let ...
zunda's user avatar
  • 1,214
1
2 回答
533 閲覧数

計数ソートを入力順にソートした際の安定性

下の疑似コードで実装された計数ソート(Counting Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか? 事実、このアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。 私は。同じ要素が複数回出現した場合に限り、その要素数-...
Avril's user avatar
  • 117
1
0 回答
272 閲覧数

バケツソートの最低ケースを改善するためには

バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか? 教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
Avril's user avatar
  • 117
0
1 回答
1,431 閲覧数

データ構造とアルゴリズムは実務ではどんなシーンで役立つのか? [クローズ済み]

現在スタック、キュー、ツリー、ソートなどを始めとしたデータ構造とアルゴリズムの勉強をしています。これはエンジニアの基礎的なスキルだから(と世間様が言ってる)という理由が私のモチベーションです。 ですがここで質問です。 質問 これらが重要と認識されてる方は、これまでご自身の開発でどのようなシーンで使ってきたか教えてもらいたいです。もしできれば、...
Akiyama Nao's user avatar
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-...
yoppy's user avatar
  • 27
0
1 回答
572 閲覧数

Judy arrayとは何ですか?

連想配列のようですが 連想配列ならmapやすでにSTLで用意されているで十分に足りると思うのですが なぜ、Judy arrayというものが生まれたのですか mapやsetと比べてそちらで用意されているものは何が大きく違うのですか?
user avatar
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. ...
user avatar
0
1 回答
187 閲覧数

データ構造のヒープへの挿入方法について

データ構造のヒープへの挿入方法で質問です。 ヒープへの挿入は、今あるノードの末尾に新しいノードを追加し、 その後、ヒープの条件を満たすような修正のオペレーションをすることだと 書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で見ました。 ネットでしらべても同様でした。 また挿入の計算量はlogH (Hは完全二分木の高さ)だとも見ました。 ここで疑問です。 ...
Akiyama Nao's user avatar
0
1 回答
154 閲覧数

文字列結合した際に、文字Kが文字aを消してしまう

現在、leetcodeの1768. Merge Strings Alternatelyを解いています。 下記が問題文(*1)と例題(*2)です 事象は、文字列結合した際に、文字Kが文字aを消してしまうことです。 コードは'(*3)にあります。 この原因と改善方法について教えていただけると幸いです。 *1 2 つの文字列 word1 と word2 が与えられます。 word1 ...
Katsu's user avatar
  • 3
0
1 回答
242 閲覧数

クイックソートのパーティションの定義について

現在、ALDS1_6_B を行っています。 解答コードは、以下のようになります。 その中で、パーティションの中で使われているint i = p-1の意味がわかりません。 なぜ、iは、p-1を行っているのでしょうか? どういう理由で、p-1を定義しているのでしょうか? また xを閾値として、for文の中で比較して、x未満とx以上を分けていると思うのですが、 なぜiを使うことで、...
Shun Takahashi's user avatar
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の右辺の表現が理解できません。この場合はどのようなグラフが期待されるのでしょうか?ご教示いただけると幸いです。
Avril's user avatar
  • 117
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&...
Katsu's user avatar
  • 3
0
1 回答
162 閲覧数

2種類のポインタを用いた線形リストの中央の要素の発見の仕方

長さが未知の線形リストの中央の要素はどのようにして見つければよいかという問題について、講義内で速いポインタと遅いポインタの2種類を使うことで見つけることが出来るという説明を講義内で受けたのですが、この速いポインタ、遅いポインタという概念について、解説がされている本やWebページなどがありましたら教えていただきたいです。
yuyu's user avatar
  • 1
0
1 回答
176 閲覧数

ダブルハッシュを使用したオープンアドレス法について

現在、AIZU ONLINE JUDEGE ALDS1_4_Cをやっています。 その中で、ダブルハッシュを使用したオープンアドレス法を学んでいます。 以下がオープンアドレス法のコードです。 #include <stdio.h> #include <string.h> using namespace std; using ll =long long; #define M ...
Shun Takahashi's user avatar
0
1 回答
218 閲覧数

Outlineビューを実現したいが、木構造を一次元のリストで表現できるような構造の名前を知りたい

概要 タイトル通り、実現したい構造があるのですが、いまいち具体的に言語化もできず、どのようにアプローチしたら良いのか分からず困っているので、以下の要件を実現できる構造をご存知であれば教えていただけると非常に助かります。 テーブルに木構造を表示するために、データを一次元配列で提供できる その際、Orderを保持できる(画像のイメージ) 定数時間での検索が可能O(1) AppendToParent, ...
Yoshiharu Yamada's user avatar
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はツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。...
Avril's user avatar
  • 117
0
3 回答
314 閲覧数

異なる文字列の接頭語と接尾語を比較

ある文字列S1、S2があるとして、S1の接尾語はS2の接頭語を反転させたものと等しいか比較し、一致する箇所だけをS2から削除したのち、その2つの文字列を連結させるというプログラムを実装したいのですが、効率的な方法はありますでしょうか。 現在は、 S1,S2を読み込む S1を反転 S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。 ...
Avril's user avatar
  • 117
0
1 回答
738 閲覧数

一つのプログラムで複数の連結リストの作成

配列を使わず、連結リスト(単方向)のみでキューのデータ構造を実装したいです。 C言語を用いて、一つのプログラムで複数の連結リストを実装することは可能でしょうか?structの定義で行き詰まってしまったので、実例も教えてくださると嬉しいです…。 追記 struct node1 { int data1; struct node1 *next1; }; struct node2 ...
Avril's user avatar
  • 117
0
1 回答
100 閲覧数

ヒープの深さと各深さにおける要素数から和を求めるプログラムのエラー

前回の質問 要素数nのヒープの深さと各深さにおける要素数を求める方法について でいただいたコメントを参考に以下のプログラムを書き、実行しましたがエラーが出ています。 エラー $ python sample.py depth_list [0, 1, 2, 3] element [1, 2, 4, 1] Traceback (most recent call last): File "...
user avatar
0
1 回答
184 閲覧数

動的計画法でナップサック問題を解く

動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。 なぜでしょうか? 1から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。 多くの解説ではdpテーブルの遷移を dp[i][p]: i-1 番目までの品物から重さが p を超えないように選んだときの、価値の総和の最大値 としていますが、これを i番目(i-...
KiYugadgeter's user avatar
  • 4,358
0
2 回答
720 閲覧数

深さ優先探索と幅優先探索の入力と使い方について

スタックを使った「深さ優先探索」とキューを使った「幅優先探索」について、入力と使い方に関してわからないことが2点あります。 現在のコードを実行するときは、2分探索木(以下の例)を入力としていますが、深さ優先探索と幅優先探索の入力は2分探索木でなければならないのでしょうか。 T = ((((), 111, ()), 11, ((), 112, ())), 1, (((), 121, ()), ...
user avatar
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 ...
SHIMASA IS OK's user avatar
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 ...
Avril's user avatar
  • 117
0
2 回答
119 閲覧数

2つのいくつかのノードを共有する連結リストをソートしたい

最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか? たとえば -900->120->200->230 \ 452->700 / -10->200 ...
Avril's user avatar
  • 117