C++

時間計算量（タイム・コンプレキシティ）とは、あるアルゴリズムが処理を完了するまでにかかる時間のことです。アルゴリズムの効率性を示す重要な指標であり、複数のアルゴリズムを比較・分析する際にも用いられます。一般的に、時間計算量を小さく抑えるほど、アルゴリズムはより効率的になります。 本記事では、C++のコードスニペットを題材に、代表的な時間計算量である O(1)、O(n)、O(n²)、O(log n)、O(n log n) を実際のコードから読み解く方法を、5つの例を通じて解説します。 例1：ループ変数が2ずつ増加する場合 → O(n) 次のコードの時間計算量を求めてみましょう。 for(i =

文字列（String）はプログラミングにおいて非常に重要な要素です。文字列とは、文字型（char）のデータが連続して並んだ配列のことを指します。GATEなどの競争試験でも頻出テーマの一つであり、確実に理解しておく必要があります。本記事では、まず文字列に関する重要なポイントを整理し、その後、概念の定着に役立つ練習問題をいくつか紹介します。 文字列の格納方法と基本ポイント C++などのプログラミング言語では、文字列を主に次の2つの方法で扱うことができます。 文字配列を使う方法：char str[size] ポインタを使う方法：char *ch = Hello のように、文字列リテラルを指すポ

配列（Array）とは 配列とは、連続したメモリ領域にデータを格納するデータ構造です。同じ型の複数の要素をインデックスで管理できるため、大量のデータを効率的に扱うことができます。 配列の宣言方法 C++では、以下の構文で配列を宣言します。 int arr1D[]; // 1次元配列の場合 int arr2D[][]; // 2次元配列の場合 重要なポイントとして、宣言時に要素数より少ない個数の値で配列を初期化した場合、残りの要素は自動的に0で初期化されます。この挙動は後述の練習問題でも登場します。 配列要素のメモリアドレス計算 配列の各要素が格納されているメモリアドレスは、次の式で

このチュートリアルでは、双方向リンクリスト（doubly linked list）のランダムポインタを修正するプログラムについて解説します。 ここでは、双方向リンクリストのうち1つのノードが誤ったポインタ（prevポインタ）を持っている状況を想定します。私たちのタスクは、ポインタが本来指すべき要素（隣接するノード）を正しく指すように修正することです。 アプローチ リストを先頭から順に走査し、各ノードについて以下の整合性を確認します。 現在のノードの next ノードの prev ポインタが、現在のノード自身を指しているか 現在のノードの prev ノードの next ポインタが、現在のノード

はじめに本記事では、n×mグリッドを塗る際の最小コストを求めるプログラムをC++で実装する方法を解説します。問題設定は以下の通りです。2つの整数 n と m が与えられ、n×m のグリッドを塗りつぶすことを考えます。このとき、1つのセルを塗るコストは「そのセルに隣接する、すでに塗られたセルの数」に等しいものとします。この条件下で、グリッド全体を塗るための最小コストを計算するのが our タスクです。考え方この問題は実はシンプルな数式で解くことができます。グリッドを塗る順序を工夫しても、隣接関係によるコストの合計は一定になるため、以下の式で求められます。最小コスト = (n - 1) × m +

このチュートリアルでは、括弧のバランスを取るために必要なコスト(最小移動回数)を求めるプログラムをC++で解説します。問題設定は次のとおりです。開き括弧「(」と閉じ括弧「)」からなる文字列が与えられ、括弧の位置を1つ移動するたびにコストが1かかるとします。このとき、文字列全体の括弧のバランスを取るために必要な最小コストを求めます。開き括弧と閉じ括弧の個数が一致しないなど、バランスを取ることが不可能な場合は -1 を出力します。アルゴリズムの考え方この問題は、累積和(プレフィックスサム)を使うことで効率的に解くことができます。手順は以下のとおりです。まず、開き括弧「(」と閉じ括弧「)」の個数をそ

はじめに このチュートリアルでは、C++を使って「文字列をパングラムにするためのコスト」を計算するプログラムについて解説します。 パングラム（パナグラム）とは、アルファベットの26文字すべてを少なくとも1回ずつ含む文や文字列のことです。有名な例として「The quick brown fox jumps over the lazy dog」が挙げられます。 問題の概要 この問題では、次の2つの入力が与えられます。 英小文字からなる文字列 各アルファベット（a〜z）を1文字追加するのにかかるコストを格納した、長さ26の整数配列 私たちのタスクは、文字列に含まれていないアルファベットを特定し、そ

本記事では、数字の「0」を含むd桁の正の整数の個数を求めるプログラムについて、C++を用いて解説します。 問題概要 整数「d」が与えられます。「0」を少なくとも1つの桁として含むd桁の正の整数が全部でいくつあるかを数え、出力することが課題です。 アルゴリズム（考え方） この問題は、すべての数を実際に列挙しなくても、組み合わせの考え方を使えば簡単に求められます。 d桁の正の整数の総数：先頭の桁は1〜9の9通り、残りの(d−1)桁はそれぞれ0〜9の10通りなので、9 × 10(d−1) 個 0をまったく含まないd桁の正の整数：各桁がすべて1〜9のいずれかになるため、9d 個 したがって、0を

このチュートリアルでは、ソート済みバイナリ配列の中から「1」の個数を求めるプログラムについて解説します。扱うデータは、0と1のみで構成された配列です。課題は、この配列内に存在する「1」の個数を効率的に数えることです。アプローチのポイント配列が「1」が先頭側、「0」が末尾側という順序でソートされている場合、先頭から順に走査する線形探索では O(n) の時間がかかります。しかし、二分探索を活用すれば、O(log n) の時間計算量で「1」と「0」の境界位置を見つけられます。アルゴリズムの流れは以下のとおりです。探索範囲の中央要素 mid を確認するarr[mid] が 1 であり、かつ arr[m

本記事では、バイナリ行列（0と1のみで構成される行列）の中から、1によって完全に囲まれている0の個数を求めるプログラムについて解説します。具体的には、0と1からなる行列が与えられたとき、行列の外側に到達できない、つまり1に囲まれて閉じ込められている0をすべて見つけ出し、その個数をカウントするのが目的です。アルゴリズムの考え方この問題は「境界からたどり着ける0」と「たどり着けない0」を区別することで解決できます。手順は以下のとおりです。1. 行列の四辺（上端・下端・左端・右端）にある0を起点として、深さ優先探索（DFS）を実行します。2. DFSで到達できた0はすべて1に書き換え、訪問済みとして

はじめにこのチュートリアルでは、C++を使って「差がkに等しい異なるペア」を見つけて数える方法を解説します。具体的には、整数型の配列と値kが与えられ、その中から差がちょうどkとなるすべての異なるペアを数えることが課題です。アルゴリズムの考え方最もシンプルなアプローチは、配列の要素を1つずつ順番に選び、それ以降の要素との差をすべてチェックする方法です。2つの要素の差がkに等しければ、カウンターを1つ増やします。例えば、配列 {1, 5, 3, 4, 2}、k = 3 の場合、差が3となるペアは (1, 4) と (5, 2) の2つなので、答えは2になります。実装例#include<ios

はじめに このチュートリアルでは、配列内の要素のうち、最初の出現以降に少なくともK回出現する要素の個数を求めるプログラムについて解説します。 問題の概要 整数型の配列と値 k が与えられます。私たちのタスクは、注目している各要素について、その要素より後方に存在する同じ値の出現回数が k 回以上であるような要素をすべて数えることです。 アルゴリズムの考え方 この問題は、以下の手順で効率的に解くことができます。 map を使用して、すでに処理済みの要素を記録し、同じ要素を二度カウントしないようにします（重複の排除）。 各要素について、それ以降の位置にある同じ値の出現回数をカウントします。 出

はじめにこのチュートリアルでは、増加する部分列（サブシーケンス）の総数を求めるC++プログラムについて解説します。0から9までの数字を含む配列が与えられます。私たちのタスクは、「次の要素が前の要素より大きい」という条件を満たす部分列の総数を数えることです。アプローチ：動的計画法この問題は、動的計画法（DP）を用いることで効率的に解くことができます。配列 count[10] を用意し、count[d] を「数字 d で終わる増加部分列の数」と定義します。配列の各要素 arr[i] を順に走査します。各ステップで、arr[i] より小さい数字 j（0 〜 arr[i]-1）で終わる部分列の数をすべ

このチュートリアルでは、配列に含まれる偶数要素と奇数要素の個数を求めるC++プログラムについて解説します。ここでは、あらかじめ整数の配列が与えられているものとします。私たちの課題は、その配列の中に偶数がいくつ、奇数がいくつ含まれているかを正確にカウントすることです。考え方基本的なアプローチは非常にシンプルです。以下の手順で処理を行います。偶数・奇数それぞれのカウント用変数を0で初期化するfor文を使って配列の全要素を先頭から順に走査する各要素を2で割った余り（剰余演算 %）を判定し、余りが0なら偶数、そうでなければ奇数としてカウントする最後に両方の結果を出力するサンプルコード#include&

このチュートリアルでは、1からnまでの整数の中に、数字「4」が含まれる数がいくつあるかを求めるプログラムについて解説します。具体的には、ある数nが与えられたとき、その範囲内で「4」という桁を少なくとも1つ持つすべての数を数え上げ、その個数を出力するのが目的です。アルゴリズムの考え方この問題はシンプルなアプローチで解くことができます。まず、1からnまでの各数値に対して、「4」という桁が含まれているかどうかを判定します。判定には、数値を10で割った余り（最下位の桁）を順番に確認していく方法を使います。もし余りが4であれば、その数には「4」が含まれていると判断できます。桁の確認が終わるまで、数値を1

二分探索木（BST）に対するイテレータを実装することを考えてみましょう。このイテレータには、次の2つのメソッドが必要です。 next()：次の要素（次に小さい値）を返すメソッド hasNext()：次の要素が存在するかどうかをブール値で返すメソッド 例えば、以下のような二分探索木があるとします。 この木に対して、関数呼び出しのシーケンスが [next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext()] である場合、出力は [3, 7, true, 9, true, 15, true,

はじめに二分木があるとき、その木を右側から見ると、特定のノードだけが見えます。この問題では、右側から見えるノードの値をすべて出力することが求められます。例えば、次のような二分木を考えてみましょう。この場合、右側から見えるのは 1 → 3 → 4 の順になります。それでは、この問題を解くためのアプローチを見ていきましょう。解法のアプローチ：DFS（深さ優先探索）を使うこの問題は、DFS（深さ優先探索）を工夫して使うことで効率的に解けます。ポイントは「各レベルで最初に到達したノード＝右端のノード」という性質を利用することです。手順まず、DFS用のヘルパーメソッドを作成します。引数として、ツリーノー

問題概要あなたはプロの泥棒だとします。ある通りに沿って建ち並ぶ家々を襲う計画を立てており、各家にはそれぞれ一定額のお金が保管されています。ただし、家々は円状に配置されており、最初の家と最後の家も互いに隣接しています。さらに、隣り合う家同士はセキュリティシステムで連結されており、同じ夜に隣接する2軒の家が泥棒に入ると自動的に警察へ通報される仕組みになっています。そこで、各家の保管金額を表す整数の配列が与えられたとき、警察に通報されずに一晩で奪える金額の最大値を求めるのがこの問題の目的です。例えば、配列が [1,2,3,1] の場合、出力は 4 となります（1番目と3番目の家を選んで 1 + 3

問題概要 1から9までの数字のみを使用して、合計がnになるk個の数字の組み合わせをすべて生成することを考えます。各組み合わせは一意な数字の集合でなければならず、使用する数字はすべて正の整数、さらに解の中に同じ組み合わせが重複して含まれていてはいけません。 たとえば k = 3、n = 9 の場合、条件を満たす組み合わせは次の3通りになります。 [[1,2,6], [1,3,5], [2,3,4]] 解法のアプローチ(バックトラッキング) この問題は、再帰を用いたバックトラッキング(探索の巻き戻し)によって効率的に解くことができます。全体の手順は以下の通りです。 solveメソッドの作成: 再

完全二分木のノード数を数える問題 完全二分木（Complete Binary Tree）が与えられたとき、その木に含まれるノードの総数を求めるのがこの問題の目的です。例えば、次のような木があった場合、出力は 6 になります。 すべてのノードを一つずつ訪問して数えれば O(n) で解けますが、完全二分木の性質をうまく利用すると、より少ない計算量でノード数を求めることができます。 解法のアプローチ ここでは再帰的なアプローチを採用します。鍵となるのは、「ある部分木について左端の高さと右端の高さが一致しているなら、その部分木は完全な満木（パーフェクトバイナリツリー）である」という完全二分木の性質で