C++

このチュートリアルでは、二分木（バイナリツリー）をそのミラーツリーへ変換するC++プログラムについて解説します。 ここでは、ある一つの二分木が与えられるものとします。私たちの課題は、木の左側と右側を入れ替えることで、与えられた二分木からミラーツリーを作成することです。 ミラーツリーとは？ ミラーツリーとは、元の木を鏡に映したように左右を反転させた木のことです。すべてのノードで左の子と右の子が入れ替わるため、中間順走査（Inorder Traversal）の結果も完全に逆順になります。 アルゴリズムの考え方 変換には再帰呼び出しを利用します。各ノードに対して、まず左右の部分木をそれぞれ再帰的に

このチュートリアルでは、二分木を変換して、すべてのノードがその右部分木に含まれる全ノードの合計値を保持するようにするプログラムについて解説します。具体的には、二分木が与えられたとき、各ノードの値が「そのノード自身の値+右部分木の合計」に等しくなるような新しい木を返すことが課題となります。アルゴリズムの考え方この問題は、再帰(後順トラバーサルの考え方)を用いることで簡潔に解くことができます。各ノードに対して以下の手順を実行します。右部分木を再帰的に変換し、その合計値を取得する左部分木を再帰的に変換し、その合計値を取得する現在のノードの値に右部分木の合計値を加算する親ノードへは「更新後のノードの値

このチュートリアルでは、二分木（バイナリツリー）を循環双方向リンクリストへ変換するC++プログラムについて詳しく解説します。与えられるのは1つの二分木です。私たちのタスクは、木の左ポインタと右ポインタをそれぞれリンクリストの「前の要素」「次の要素」に対応させ、中間順走査（Inorder Traversal）の順序をそのまま循環リンクリストの並びとして実現することです。アルゴリズムの考え方この問題は再帰を利用するとシンプルに解けます。処理の流れは以下の通りです。左部分木を再帰的に循環リンクリストへ変換する右部分木を再帰的に循環リンクリストへ変換する現在のノードを、自分自身の左右ポインタを自分に向

このチュートリアルでは、キュー（queue）データ構造を利用して、通常の二分木をスレッド化二分木（Threaded Binary Tree）へ変換するプログラムについて解説します。 スレッド化二分木とは？ スレッド化二分木とは、右の子を持たないノードのNULLポインタ部分を、「中順走査（inorder traversal）における次のノード（中順後続ノード）」への参照に置き換えた二分木のことです。これにより、再帰やスタックに頼らずに効率的な中順走査が可能になります。 今回の課題は、与えられた二分木に対して、キューを活用して中順走査を高速化するための追加リンク（スレッド）を設定し、スレッド化

はじめに この記事では、二分探索木(BST)を、「各ノードのキーに、そのキーより大きいすべてのキーの合計を加算した二分木」へ変換するC++プログラムを解説します。 問題の概要 入力として与えられるのは二分探索木です。私たちのタスクは、この木を、各ノードの値が「元の値 + 自分より大きいすべてのキーの合計」に置き換えられた二分木へと変換することです。 例えば、次のようなBSTを考えてみましょう。 5 / \ 2 13 この場合、変換後の各ノードの値は以下のようになります。 13 → 13(自分より大きいキーが存在しないため、そのまま) 5 → 5

はじめに：二分探索（バイナリサーチ）とは二分探索（バイナリサーチ）は、配列の中央の値と目的の要素を比較し、その結果に応じて探索範囲を半分に絞り込んでいく検索アルゴリズムです。この処理を要素が見つかるまで繰り返すことで、高速な検索を実現します。ただし、二分探索を適用するには配列がソート済みであることが前提条件となります。整列されていないデータに対しては使用できない点に注意しましょう。二分探索の計算量は対数時間 O(log n) であり、非常に効率的です。そのため、プログラマーにとってはアルゴリズムを自前で実装するだけでなく、標準テンプレートライブラリ（STL）に用意された便利な関数を使いこなすこ

二分探索（バイナリサーチ）は「対数探索」とも呼ばれる検索アルゴリズムで、ソート済みの配列から特定の要素を効率よく探し出す手法です。配列を再帰的に半分に分割しながら探索範囲を絞り込み、中央の位置に目的の要素が見つかればその位置を返し、見つからなければ分割と照合を繰り返します。探索のたびに候補が半分に減っていくため、計算量はO(log n)と非常に高速です。 二分探索の仕組み このアルゴリズムは、ソート済み配列の中央の要素と、探したい要素を比較することで動作します。 探索対象の要素が中央の要素と等しい場合 → その要素のインデックス（位置）を返します。 探索対象の要素が中央の要素より大きい場合 →

単一連結リスト（片方向リンクリスト）とは、各ノードが「値」と「次のノードのメモリ位置」を保持するデータ構造であり、一方向にしかたどることができない連結リストのことです。 二分探索（バイナリサーチ）は、分割統治法に基づく探索アルゴリズムです。データ構造の中央要素を取り出して探索対象の値と比較し、一致しなければ、同じアルゴリズムを上半分または下半分に再帰的に適用しながら探索範囲を絞り込んでいきます。 ここでは、単一連結リストと探索対象の値が与えられ、二分探索によってその値を検索します。 単一連結リストはポインタを1つしか持たないデータ構造のため、中央の要素を直接取得するのは容易ではありません。そ

二分探索木（BST：Binary Search Tree）は、以下のルールに従う特殊な木構造のデータ構造です。 左の子ノードの値は、常に親ノードの値より小さい 右の子ノードの値は、常に親ノードの値より大きい すべてのノードが、それぞれ個別に二分探索木の条件を満たしている 二分探索木（BST）の例： 二分探索木は、検索や最小値・最大値の探索といった操作の計算量を削減するために用いられるデータ構造です。比較のたびに探索範囲が半分に絞られていくため、バランスの取れた木であれば、平均的にO(log n)の時間計算量で各操作を完了できます。 BSTにおける検索操作 二分探索木でキーを検索する際は

二分探索木（BST）とは二分探索木（Binary Search Tree：BST）は、以下のルールに従う特殊な木構造のデータ構造です。左の子ノードの値は、常に親ノードの値より小さい右の子ノードの値は、常に親ノードの値より大きいすべてのノードが個別に二分探索木の条件を満たす二分探索木（BST）の例：二分探索木は、検索や最小値・最大値の探索といった操作の計算量を削減するために用いられるデータ構造です。木の構造そのものが値の大小関係を保持しているため、効率的な探索が可能になります。二分探索木（BST）の削除操作削除操作とは、指定したノードを木から取り除くことです。ノードを削除する場合、削除対象のノー

二分木（Binary Tree）とは二分木とは、木構造の各ノードが最大で2つの子ノードを持つことができる特別な木構造です。これらの子ノードは、それぞれ「左の子ノード」と「右の子ノード」と呼ばれます。シンプルな二分木の例は以下の通りです。二分探索木（BST）とは二分探索木（BST）は、以下のルールに従う特別な木構造です。左の子ノードの値は、常に親ノードの値より小さい右の子ノードの値は、常に親ノードの値より大きいすべてのノードが、それぞれ独立して二分探索木の性質を満たす二分探索木（BST）の例は以下の通りです。二分探索木は、検索や最小値・最大値の探索といった操作の計算量を削減するために用いられるデ

確率変数とは 確率変数とは、複数の結果が生じうるプロセスの実行結果を表す変数のことです。例えば、コインを1回投げたときに「表」か「裏」のどちらが出るかを表す変数は、典型的な確率変数といえます。 二項確率変数は、確率変数の中でも特殊な種類であり、ある試行において結果が固定した確率で生じる事象に関連する値を持ちます。 二項確率変数が満たすべき4つの条件 ある変数が二項確率変数と呼ばれるためには、以下の性質をすべて満たしている必要があります。 試行の総回数が固定されていること 各試行の結果は「成功」か「失敗」のいずれかであり、中間の結果が存在しないこと 各試行における成功確率が常に同じであること

問題概要本記事では、C++を用いて「与えられた文字列から作成できる、重複のないソート済み順列（distinct sorted permutations）をすべて出力する」というプログラミング問題を解説します。この問題には、次の2つの条件があります。文字列には、同じ文字が複数回現れる場合がある（重複あり）。入力される文字列は、あらかじめソートされた順序で与えられる。具体的なイメージをつかむために、入出力の例を見てみましょう。入力 : ABD出力 : ABD, ADB, BAD, BDA, DAB, DBA入力 : RSTU出力 : RSTU, RSUT, RTSU, RTUS, RUST, RU

この問題では、ユーザーから与えられた一定の範囲内にとどまるように、正方向または負方向への有効な移動手順を見つける必要があります。具体的には、移動できる最大値を示す上限 K と、n 個の正の値からなる移動量の配列が与えられます。それぞれの移動量に対して正方向・負方向のどちらに進むべきかを判定し、位置が一度も上限 K を超えないような方向の列を出力することが求められます。具体例を使って、このトピックをより深く理解していきましょう。入力 : K = 56、配列 = [25, 14, 31, 16, 5] 出力 : positive positive negative positive positiv

この問題では、与えられた数値から1桁を削除し、削除後にできる新しい数値が6で割り切れるようにします。そして、削除すべき桁の位置を出力します。概念をより深く理解するために、例を見てみましょう。入力 : 1324出力 : 4説明 − 4桁目を削除すると「132」が得られ、これは6で割り切れます。つまり、数値が与えられたとき、6で割り切れるようにするために削除すべき桁の位置を返す必要があります。この問題を解くために、ロジックを組み立てていきます。その際、「ある数が2と3の両方で割り切れるならば、その数は6で割り切れる」という性質を利用します。桁を削除した後にできる新しい数値について、6で割り切れるか

二分木（バイナリツリー）とは二分木とは、各ノードが最大で2つの子ノードを持つ特別な木構造です。つまり、すべてのノードは葉ノードであるか、1つまたは2つの子ノードを持ちます。例：問題の概要この問題では、二分木とその木の中の1つのノードが与えられ、そのノードの「いとこノード（cousin nodes）」を見つけて出力することが求められます。ただし、兄弟ノードは出力の対象外です。具体例を見てみましょう。上記の二分木において、対象ノードのいとこノードは5です。いとこノードとは概念をより明確にするために、いとこノードについて説明します。二分木において、2つのノードが同じレベル（深さ）に位置し、かつ同じ親

この問題では、文字列が与えられ、連続する文字（アルファベット順で隣り合う文字）が2つ以上続く場合はそれらを同じ行にまとめて出力し、連続していない場合は改行して別の行に出力する必要があります。まず例を見ながら、この概念をより深く理解しましょう。入力 : abcxstk 出力 : abc x st k解説 − 「abc」は連続しているため、1行に出力されます。次の「x」は連続していないため、ここで改行が入ります。次の「s」は「x」と連続していないため、改行して出力します。次の「t」は「s」と連続しているため、続けて出力されます。最後の「k」は「t」と連続していないため、改行して出力します。この問題

はじめに この記事では、2次元マトリックス内にお互いが同心（同じ中心を持つ）になるように長方形パターンを出力する方法を解説します。 まず、具体例を見ながら問題を理解しましょう。 n = 4 の場合 : 4 4 4 4 4 4 4 4 3 3 3 3 3 4 4 3 2 2 2 3 4 4 3 2 1 2 3 4 4 3 2 2 2 3 4 4 3 3 3 3 3 4 4 4 4 4 4 4 4 このように、整数値 n を入力として受け取り、外側から内側へと値が1ずつ減少していく同心の長方形パターンを出力します。一般化すると次のような形になります。 n n n n n n n

この問題では、文字列が与えられ、ジグザグパターンの行数nも指定されます。そして、その文字列をn行のジグザグパターンに配置したとき、各行の文字を読み取って連結した結果を出力する必要があります。 具体例を見ながら、この概念をより深く理解していきましょう。 例1 入力 : 文字列 = STUVWXYZ、 n = 2 出力 : SUWYTVXZ 解説 − この文字列を2行のジグザグパターンに配置すると、以下のようになります。 S U W Y T V X Z このジグザグパターンを行ごとに連結すると、「SUWYTVXZ」となります。上の行（S, U

この記事では、二分木とその中の2つのノードが与えられたときに、ルートから各ノードへの経路上に存在する共通ノード、すなわち両ノードの共通祖先をすべて出力する方法を解説します。 二分木とは？ 二分木（Binary Tree）とは、すべてのノードが最大2つの子ノードを持つことができる特殊な木構造です。つまり、各ノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。 祖先ノードとは？ 祖先ノードとは、木構造において、より下位の階層にあるノードと接続されているノードのことを指します。 共通祖先ノードとは？ 2つのノードの共通祖先ノードとは、木の中で両方のノードにとって祖先となるノードの