C++

2値行列(バイナリ行列)を想定してみましょう。本記事では、行列の中から重複する行を効率よく見つける方法を解説します。例として、次のような行列を考えます。 110101001001101100110101001001001001 この行列では、0始まりで数えて位置3、4、5の行が互いに重複しています(1行目と4行目、2行目・5行目・6行目がそれぞれ同じ内容です)。 解決のアプローチ:Trie(トライ木)を活用する この問題を解くには、Trie(トライ木)と呼ばれるデータ構造を利用します。Trieは、扱う値の種類が少ないデータの格納と検索に適した効率的な構造で、検索の計算量はキーの長さに対してほぼ

問題の概要この問題では、n×mサイズの2次元行列を作成します。行列には母音だけを配置し、すべての行とすべての列に5つの母音(a・e・i・o・u)が必ず含まれるようにする必要があります。「すべての母音が含まれる」という条件を満たすには、a・e・i・o・uの5文字が最低限必要となるため、行列の行数と列数はどちらも5以上でなければなりません。つまり、作成できる最小の行列は5×5です。それでは、具体例を使って問題をより深く理解しましょう。例1入力 : N = 5、M = 5 出力 : a e i o u e i o u a i o u a e o u a e i

整数 N が与えられたとき、N の約数の中から4つを選び、次の2つの条件を同時に満たす組み合わせの積を求めることを考えます。選んだ4つの約数の合計が N に等しいこと4つの約数の積が最大になること例として N = 24 の場合を考えてみましょう。24 の約数は 1, 2, 3, 4, 6, 8, 12, 24 です。この中から「6」を4回選ぶと、6 + 6 + 6 + 6 = 24 という合計になり、このときの積は 6 × 6 × 6 × 6 = 1296 となり、これが最大値になります。解法のアプローチこの問題を解くには、まず 1 から N までの各整数について約数をすべて求め、その上で以下

リンクリスト（連結リスト）とはリンクリストは、各要素（ノード）をメモリ上の連続しない領域に格納できる線形データ構造です。各ノードにはデータ本体と、次のノードを指すポインタが含まれており、ポインタをつなぐことで一連のリストとして扱うことができます。問題の概要今回は、与えられたリンクリストを走査し、交互（ひとつおき）のノードだけを出力するプログラムを作成します。具体的には、1番目・3番目・5番目…というように、奇数番目の要素のみを順に出力していきます。入出力例入力 : 2 -> 4 -> 1 -> 67 -> 48 -> 90 出力 : 2 -> 1 ->

この問題では、キャメルケース（CamelCase）で記述された文字列の配列とパターンが与えられ、そのパターンに一致する配列内のすべての文字列を出力することが求められます。 用語の説明 文字列の配列とは、要素がすべて文字列型である配列のことです。 キャメルケース（camelCase）は、プログラミングで広く使われている命名規則の一つです。複合語を表記する際に、2語目以降の先頭文字を大文字にし、残りの文字を小文字で記述します。 例：iLoveProgramming 問題の定義 課題：指定されたパターンに一致するすべての文字列を見つけ出すことです。 入出力例 入力： TutorialsPoint,

この問題では、与えられた文字列を部分文字列に分割し、それぞれを括弧で囲んで出力する必要があります。まず、具体例を見ながら問題を理解しましょう。入力 : wxyz 出力 : (w) (x) (y) (z) (w) (x) (yz) (w) (xy) (z) (w) (xyz) (wx) (y) (z) (wx) (yz) (wxy) (z) (wxyz)解説 − 文字列を考えられるすべての部分文字列の組み合わせに分割し、それぞれの部分文字列を括弧で囲んで表示します。長さ n の文字列の場合、分割パターンは 2n-1 通り存在します。

問題の概要0と1のみで構成される2値行列が与えられたとします。この行列の中に、4つのコーナー（角）がすべて1である長方形が存在するかどうかを判定するのが、本記事のテーマです。例として、次のような行列を考えてみましょう。10010001010001010101この行列の場合、答えは「はい」となります。実際に、コーナーがすべて1である長方形が存在します。101010101上の部分行列に注目すると、左上・右上・左下・右下の4つのコーナーがすべて1になっていることが確認できます。解決のためのアプローチこの問題を効率的に解くために、ハッシュセット（unordered_set）を活用した手法を採用します。

問題の概要 この問題では、単語の集合と文字の配列が与えられ、その配列に含まれる文字だけを使って作成できる単語をすべて見つけ出します。 入力と出力の例 入力 : words[] : {go , hi , run , on , hog , gone} Char[] : {a , o , h , g} 出力 : go , hog 説明: 与えられた単語の中で、文字配列 {a, o, h, g} のみで構成できるのは「go」と「hog」の2つです。「hi」や「run」などは配列に存在しない文字を含むため、有効な単語として出力されません。 解決アプローチ:トライ(Trie)データ構造 この

直線が y = mx + c という形式で複数本与えられているとします。これらの直線と垂直区間(縦方向の帯状領域)を考え、指定された区間内に直線同士の交点が存在するかどうかを判定します。例として、次のような直線があるとします。L1 = y = x + 2L2 = y = -x + 7L3 = y = -3L4 = y = 2x - 7そして、垂直区間は x = 2 から x = 4 までとします。この場合、L1 と L2 の交点はこの区間内に存在するため、答えは true となります。解法の考え方この問題は、ソートのテクニックを使うことで効率的に解けます。まず、各直線と垂直区間の両端(左境界・

問題の概要 サイズ m と n の正整数からなる2つの配列があるとします（m > n）。この問題の目的は、2つ目の配列に 0 を挿入することで、2つの配列の内積を最大化することです。ただし、元の配列内の要素の順序を入れ替えることはできません。 例として、配列 A = [2, 3, 1, 7, 8] と配列 B = [3, 6, 7] を考えてみましょう。このときの出力は 107 となります。B の1番目と3番目の位置に 0 を挿入すると、内積は 2 × 0 + 3 × 3 + 1 × 0 + 7 × 6 + 8 × 7 = 107 となり、これが最大値になります。 動的計画法によるアプロ

ここでは、n個のオブジェクトからなる配列を扱います。各オブジェクトは幅 W[i] を持っており、これらを次の条件を満たすようにピラミッド状に配置することを考えます。i番目のレベルの合計幅は、(i+1)番目のレベルの合計幅より小さいことi番目のレベルに含まれるオブジェクトの数は、(i+1)番目のレベルより少ないこと例えば、重みが [40, 100, 20, 30] の場合、答えは 2 になります。最上部のレベルには 30 を置き、その下のレベルには 20 と 40、さらにその下に 100 を配置します。貪欲法によるアプローチこの問題を解くには、貪欲法(グリーディ法)が有効です。基本的なアイデアは

正の整数からなる3つのスタックが与えられたとき、先頭要素の削除を許可して、3つのスタックの合計が等しくなる最大値を求める問題を考えてみましょう。スタックは配列として表現され、配列の最初のインデックスがスタックの先頭（トップ）の要素を表します。例として、スタックの要素が [3, 10]、[4, 5]、[2, 1] である場合を考えます。この場合の出力は 0 になります。なぜなら、3つのスタックすべてから全要素を削除しない限り、合計を等しくできないからです。アルゴリズムの考え方この問題を解くための基本的なアイデアは、各スタックの合計値を比較し、等しくなければ合計が最大のスタックから先頭要素を削除す

正の整数からなる2つの配列 X と Y が与えられます。このとき、x^y > y^x を満たすペア（x, y）の総数を求めるのが本記事のテーマです。ここで、x は配列 X の要素、y は配列 Y の要素を表します。 例として、X = [2, 1, 6]、Y = [1, 5] の場合を考えてみましょう。このとき出力は 3 になります。条件を満たすペアは (2, 1)、(2, 5)、(6, 1) の3つだからです。 効率的な解法のポイント すべての組み合わせを総当たりで調べる方法もありますが、計算量が O(m × n) となり、配列が大きくなると非効率です。そこで役立つのが、次の数学的な性質

文字列が与えられたとき、その文字列を左右に分割した際に、左側と右側の両方に同じ種類の文字が含まれる分割位置(バランス位置)の数を求める問題について解説します。なお、文字の出現頻度は問われず、文字の種類が一致していればよい点に注意してください。例えば、文字列が「ABAABA」の場合、バランス位置の数は 3 となります。具体的には、以下の3つの分割位置が該当します。AB | AABAABA | ABAABAA | BAアルゴリズムの考え方この問題は、以下のような効率的なアプローチで解くことができます。まず文字列全体を走査し、すべての文字の出現回数を right[] 配列に記録します。次に、文字列を

この記事では、C++でユーザーから整数値を入力として受け取り、それを画面に表示する方法を解説します。標準入力を受け取るには iostream ヘッダーに含まれる cin を使用し、出力には cout を使用します。cin では抽出演算子（>>）を、cout では挿入演算子（<<）を使うのが基本です。 入力の基本構文は次のとおりです。 int x; cin >> x; 出力の基本構文は次のようになります。 int x = 110; cout << x; サンプルコード 以下は、ユーザーからの入力値を読み取り、あらかじめ初期化した変数と一緒に出力す

この記事では、C++の技術面接で頻出する重要な質問をいくつか取り上げ、それぞれのポイントをわかりやすく解説します。面接対策の復習用としても活用できる内容になっています。 C言語とC++の違いは何ですか? C言語とC++は文法が似ていますが、設計思想やサポートする機能に大きな違いがあります。主な相違点を以下の表にまとめました。 項目CC++ 開発の経緯デニス・リッチーによって1969年頃、AT&Tベル研究所で開発されました。ビャーネ・ストロヴストルップによって1979年に開発されました。 言語タイプ手続き型プログラミング言語です。手続き型とオブジェクト指向の両方のプログラミン

本記事では、システムコールを利用してC++でタイマー（ストップウォッチ）を作成する方法を解説します。グラフィックスやアニメーションライブラリは一切使わず、標準的なシステムコールだけで動作するシンプルな実装です。ここでいう「タイマー」とは、時間を0からカウントアップしていくストップウォッチ形式のものを指します。使用するシステムコールこのプログラムでは、以下の2つのシステムコール（関数）を使用します。sleep(n) … プログラムの実行をn秒間一時停止（スリープ）させます。1秒ごとに表示を更新するために利用します。system() … 引数として渡した文字列をシステムコマンドとして実行します。こ

本記事では、C++を学ぶべき理由について詳しく解説します。C++は世界で最も人気のあるオブジェクト指向プログラミング言語のひとつであり、さまざまな分野で活用されています。ここでは、多くのエンジニアがC++を選ぶ主な理由を7つに分けてご紹介します。 1. C++の人気と高年収 C++は世界で最も人気のあるプログラミング言語のひとつで、世界中で約440万人の開発者が利用しています。C++開発者は業界でも特に高収入な職種に位置しており、平均年収は10万ドル（約1,500万円）に達するとも言われています。 2. 豊富なライブラリサポート（STL） C++には標準テンプレートライブラリ（STL）が用意さ

C++には、異なるデータ型同士を扱う際に欠かせない「型変換（タイプコンバージョン）」の仕組みが備わっています。型変換には主に2種類あり、それぞれ暗黙的型変換（implicit conversion）と明示的型変換（explicit conversion）と呼ばれます。本記事では、それぞれの型変換の特徴や動作の違いを、具体的なコード例とともにわかりやすく解説します。暗黙的型変換（自動型変換）とは暗黙的型変換は「自動型変換」とも呼ばれ、プログラマが特別な指示を出さなくても、コンパイラが自動的に行う型変換のことです。一つの式の中に複数のデータ型が混在している場合に、この変換が発生します。変換の際、す

問題の概要2つの整数 x と n が与えられたとき、x1, x2, …, xn の各値に出現する数字（0〜9）の頻度を格納した配列を作成することを考えます。例えば、x = 15、n = 3 の場合を見てみましょう。x1 から xn までの値は以下のとおりです。151 = 15152 = 225153 = 3375これらの値に含まれる各数字の出現回数を集計すると、結果は [0, 1, 2, 2, 0, 3, 0, 1, 0, 0] となります。この配列の各要素は、インデックス0〜9に対応する数字が何回出現したかを表しています。解決の手順この問題は、以下の手順で解くことができます。0〜9の数字の出