C++

凸包(とつほう)とは、平面上に与えられたすべてのデータ点を包含できる最小の閉領域のことです。 グラハムスキャン(Graham Scan)アルゴリズムは、この凸包の境界となる頂点を効率的に求める古典的な手法です。まず、最も下にある点(y座標が最小の点)を選び、それを凸包の開始点とします。続いて、残りのn-1個の頂点を、開始点から見た反時計回りの角度に基づいてソートします。同じ角度を持つ点が複数ある場合は、開始点から最も遠い点を除いてすべて取り除きます。 その後、残りの点を順にスタックへプッシュしていきます。スタックの最上位の点・その下の点・新しく選択した点points[i]の3点が反時計回りにな

ジャービスマーチ（Jarvis March）アルゴリズムは、与えられた点の集合から凸包（Convex Hull）の頂点、すなわち境界となる角の点を検出するための手法です。まずデータセットの中で最も左側にある点を起点とし、そこから反時計回りに回転しながら凸包に含まれる点を順番に選んでいきます。現在の点から次の点を選ぶ際には、各候補点の方向（向き）を外積によって判定し、角度が最大になる点を採用します。すべての点を巡り、次の点が再び始点に戻った時点でアルゴリズムを終了します。入力：点の集合 {(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), (4,-6), (

最長増加部分列（Longest Increasing Subsequence：LIS）とは、数列の中から一部の要素を取り出して作った部分列のうち、各要素が直前の要素よりも常に大きくなるような列のことです。本記事では、整数の集合が与えられたときに、その最長増加部分列の長さを動的計画法（DP）を用いて求める方法を解説します。問題の例入力：整数の集合 {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} 出力：最長増加部分列の長さ → 6 該当する部分列は 0, 2, 6, 9, 13, 15アルゴリズムの考え方この問題は動的計画法を使って効率

C++では、オブジェクトを関数に渡す方法が複数あり、それぞれ動作やパフォーマンスの特性が異なります。ここでは、クラス X のオブジェクトを関数 fun に渡す場合を例に、代表的な渡し方をひとつずつ解説します。 1. 値渡し（Pass by Value） 値渡しでは、関数のスコープ内にオブジェクトのコピー（シャローコピー）が新しく作成されます。そのため、関数内でオブジェクトをどれだけ変更しても、呼び出し元の元のオブジェクトには一切影響しません。なお、ポインタメンバを持つクラスの場合、浅いコピーが作られる点には注意が必要です。 宣言 void fun(X x); 呼び出し X x; fun(x)

C++のプログラムを作成していると、int main(int argc, char *argv[])という形式のmain関数を目にすることがあります。ここで、argcは「argument count（引数の個数）」、argvは「argument values（引数の値）」を意味しています。これらは、プログラムの実行開始時にmain関数へ渡される変数です。プログラムを実行する際、コマンドラインから引数を渡すことができます。例えば以下のように実行します。$ ./a.out helloこの場合、「hello」が実行ファイルに渡される引数となります。この引数は、プログラム内からアクセスして利用すること

はじめにC++には複数のキャスト演算子が用意されており、それぞれ目的と安全性が異なります。この記事では、特によく使われる static_cast、dynamic_cast、そして従来の通常のキャスト（Cスタイルキャスト）の違いをわかりやすく解説します。さらに、const_cast と reinterpret_cast についても併せて紹介します。static_cast（静的キャスト）static_cast は、通常の型変換を行うための最も基本的なキャストです。暗黙的な型変換（型強制）にも対応しており、明示的に記述することもできます。例えば、float を int に変換する場合や、char を

「struct」と「typedef struct」の基本的な違い基本的に、structは構造体を定義するために使用されるキーワードです。しかし、C言語では、定義した構造体を実際に使用する際に、必ずstructキーワードを付けて記述する必要があります。一方、typedefキーワードを組み合わせて使用すると、構造体に新しい別名（型名）を与えることができます。これにより、以降はその名前だけで構造体を利用でき、いちいちstructキーワードを書く必要がなくなります。C言語での記述例// structのみを使用する場合 struct Point { int x; int y; }; s

データ隠蔽（データハイディング）は、オブジェクト指向プログラミング（OOP）の重要な機能の一つです。これにより、クラス型の内部表現へプログラム内の関数が直接アクセスすることを防ぐことができます。 クラスメンバーへのアクセス制限は、クラス本体内に記述する「public」「private」「protected」というアクセス指定子によって指定します。 メンバーおよびクラスのデフォルトのアクセスレベルはprivateです。 サンプルコード class Base { public: // ここにpublicメンバーを記述 protected: // ここにprot

C++のインクリメント演算子には、前置（++i）と後置（i++）の2つの形式があり、この2つには動作面で大きな違いがあります。本記事では、両者の基本的な挙動の違いをサンプルコードとともに解説し、あわせてパフォーマンスへの影響についても見ていきます。 前置演算子と後置演算子の基本的な違い 前置バージョン（++i）： iの値を先にインクリメントし、式の値としてはインクリメント後の新しい値を返します。つまり「まず増やしてから、その値を式に代入する」という動作になります。 後置バージョン（i++）： i自体はインクリメントされますが、式の値としては元の値を返します。つまり「まず元の値を式に使ってから

2部グラフ（Bipartite Graph）とは、グラフ全体を2色だけで彩色できるグラフのことです。つまり、頂点を2つの集合に分け、同じ集合内の頂点にはすべて同じ色が割り当てられます。この記事では、2部グラフを入力として受け取り、各頂点に彩色を行った結果を出力するC++プログラムを紹介します。アルゴリズムBegin 幅優先探索（BFS）を使ってすべての頂点を走査します。 1つの頂点を選び、黄色に塗ります。 その隣接する頂点をすべて青色に塗ります。 次のレベルの頂点は黄色に塗り、これを全頂点が彩色されるまで繰り返します。 End.サンプルコード#include<bi

無向グラフ G の線グラフ（Line Graph） L(G) とは、元のグラフ G における辺同士の隣接関係を表す別のグラフです。線グラフでは、G の各辺が頂点となり、G で共有する端点を持つ（つまり接している）2つの辺は、L(G) 内で互いに隣接する頂点として結ばれます。本記事では、入力されたグラフから線グラフを生成し、その線グラフに対して辺彩色（Edge Coloring）を行うC++プログラムを紹介します。辺彩色とは、隣接するどの2つの辺も同じ色にならないように、グラフの辺に色を割り当てる問題です。アルゴリズムプログラムの処理の流れは以下のとおりです。Begin 　　1. 頂点数「n」と

DAG（有向非巡回グラフ）とは有向非巡回グラフ（DAG：Directed Acyclic Graph）とは、辺に向きが定義された有向グラフであり、かつグラフ内にサイクル（閉路）が存在しないグラフのことです。すべての辺は一方向のみに向かっており、どの頂点から出発しても同じ頂点へ戻ってくる経路は存在しません。DAGは、タスクのスケジューリング、依存関係の解決、トポロジカルソートなど、さまざまな分野で活用されています。本記事では、与えられたグラフがDAGであるかどうかを判定するC++プログラムを紹介します。アルゴリズムこのアルゴリズムでは、出次数が0（隣接リストが空）の頂点を順に取り除いていくことで

この記事では、C++を用いてグラフ構造化スタック（Graph Structured Stack）を実装する方法を解説します。グラフ構造化スタックは、複数のスタックの状態を有向グラフとして管理できるデータ構造であり、GLR構文解析などのパースアルゴリズムで利用されることで知られています。本プログラムでは、隣接行列で表現されたグラフ上を探索し、始点ノードからボトムノードに至る経路を複数のスタックとして検出・出力します。アルゴリズムの手順adjMat[sVertex][dVertex] = adjMat[sVertex][dVertex] 繰り返し終了 繰り返し終了

これは、ビット配列（Bit Array）をC++で実装するプログラムの解説です。ビット配列とは、データを1ビット単位でコンパクトに格納できる配列データ構造の一種で、シンプルなデータ構造を実装するために広く利用されます。各要素が0か1の値のみを保持するため、通常の整数型配列と比べてメモリを大幅に節約できる点が大きな特徴です。 アルゴリズム 使用する関数と擬似コード： Begin Function getBit(int val,int pos) // valのpos番目のビットを取得 singleBit->b = 0 if(pos == 0) sin

C++において、ソートされた配列はソートされていない配列よりも高速に処理できます。その理由は「ブランチ予測（分岐予測）」にあります。コンピュータアーキテクチャにおけるブランチ予測とは、プログラムの命令フロー内にある条件分岐（ジャンプ）が実行されるかどうかを、CPUが事前に推測する仕組みのことです。この予測が当たればパイプライン処理が中断されずに済み、処理速度が大きく向上します。具体例で見てみよう以下のようなコードを考えてみます。if(arr[i] > 50) { 操作Bを実行 } else { 操作Aを実行 }このコードを、ソート済みの配列と未ソートの配列に対してそれぞれ10

動的な2次元配列とは、基本的に「配列へのポインタ」を要素とする配列（ポインタの配列）のことです。つまり、各行が独立した1次元配列としてヒープ上に確保され、それらの先頭アドレスを格納するポインタ配列によって全体が管理されます。下図は、3×4の2次元配列のイメージです。アルゴリズムC++のnew演算子で2次元配列を動的に確保する手順は以下の通りです。Begin 配列の寸法（行数・列数）を宣言する。 new を使って 2次元配列 a[][] を動的に確保する。 配列に要素を代入する。 配列の内容を出力する。 delete でメモリを解放する。 Endサンプルコ

C++では、配列をそのまま関数の引数として渡すことができます。本記事では、2次元配列を関数に引き渡して、その要素をすべて表示するプログラムを紹介します。 アルゴリズム Begin 2次元配列 n[][] を関数 show() に渡す。 show() 関数内で、二重の for ループ（ネストされたループ）を使って配列 n の全要素を走査する。 End サンプルコード #include <iostream> using namespace std; void show(int n[4][3]); int main() { int n[4][3] = {

C++における動的メモリ管理では、new演算子がヒープメモリ上にオブジェクトや配列を確保し、delete／delete[]演算子がそのメモリを解放します。ここでよく疑問に挙がるのが、「delete[]は引数としてポインタしか受け取っていないのに、なぜ配列の要素数（サイズ）を正しく把握できるのか？」という点です。 delete[]がサイズを認識できる仕組み 答えはシンプルで、new[]演算子が確保時に要素数をどこかに記録しており、delete[]はその記録を参照してメモリを解放するからです。 具体的には、多くのコンパイラ実装では、new int[n]のように配列を確保するとき、ユーザーが要求した

C++は可変長配列（VLA）をサポートしているのか？結論から言うと、C++は可変長配列（Variable Length Array：VLA）を標準規格としてはサポートしていません。C++11以降の標準では、配列のサイズは「定数式（constant-expression）」である必要があると明確に定められています。そのため、次のように引数で受け取った値を実行時に配列サイズとして使うコードを書いた場合、標準に準拠したコンパイラではコンパイルエラーとなります。void displayArray(int n) { int arr[n]; // nは定数式ではないためエラー // ....

C++では、関数から配列そのものを返すことができません。なぜそうなっているのか、具体的なプログラム例を見ながら解説します。問題となるサンプルコードまず、次のプログラムを見てください。ローカル配列のアドレスを返そうとしている例です。#include <iostream> using namespace std; int* Array() { int a[100]; a[0] = 7; a[1] = 6; a[2] = 4; a[3] = 3; return a; // ローカル変数のアドレスを返している } int main()