マージソートのアルゴリズムとその実装
配列マージの基本
マージソートの核となる処理は、すでに整列済みの2つの部分配列を効率的に結合することです。たとえば、ar1[] = {1,2,3,4} と ar2[] = {3,4,5,6,7} の2つの配列があるとします。これらを効率的にマージするには、それぞれの配列にポインタを用意しておき、値を比較しながら新しい配列に格納していきます。
#include <stdio.h>
#include <stdli ...
5月14日 18:52 投稿
グラフ理論における第二最短経路
前提知識
グラフの表現方法、最短経路探索アルゴリズム、幅優先探索(BFS)の理解が必要です。
第二最短経路の分類
一般第二経路（同一辺の重複利用可能）
単純第二経路（同一辺の重複利用不可）
厳密/非厳密第二経路（最短経路と等価/非等価）
一般第二経路
配列の最大値・次大値探索と類似した手法を用います。各頂点について最短距離と第二短距離を同時に管理します。 ...
5月14日 18:44 投稿
C言語によるデータ構造の実装とアルゴリズム設計
線形リストの特性と比較
配列ベースリストの特徴
配列を用いたリストはメモリ空間を事前に確保する必要があるため、サイズ変更が難しいが、要素へのアクセスは定数時間で可能である。挿入や削除を行う際には、対象位置以降のすべての要素を移動させる必要があり、処理効率が低下する可能性がある。
単方向連結リストの特徴
連結リストは動的メモリ割り当てにより柔軟なサ ...
5月14日 18:06 投稿
バイナリツリーの基礎理論と再帰的走査アルゴリズム
バイナリツリーの基本概念
バイナリツリーは計算機科学における重要なデータ構造であり、多くのアルゴリズムでスタックを用いて実装されます。
バイナリツリーの分類
完全二分木 (Full Binary Tree)
すべてのノードが0個または2個の子ノードを持ち、すべての葉ノードが同じ深さにある二分木を完全二分木と呼びます。深さkの完全二分木は2^k-1個のノードを持ちます。
完 ...
5月14日 12:57 投稿
動的計画法入門：基本概念と実践
動的計画法(DP)は前の状態から次の状態を導き出す手法であり、貪欲法が局所的に最適解を選択するのとは異なります。アルゴリズム学習において、この違いを理解することが重要です。
動的計画法問題を解決するため、以下の5つのステップを確実に理解する必要があります。これら全てをマスターしてこそ、動的計画法を真に理解したと言えます。
DP配列（テーブル）と添字 ...
5月14日 05:35 投稿
Pythonクリエイティブプロジェクトデザインとプログラミング例集
Python言語を使用したクリエイティブなプログラミングプロジェクトと実践例を紹介します。以下に、様々なプログラミング課題とその実装例を示します。
目次
1. 百点満点の成績を入力する
2. バスケットボール試合のケース
3. y=1+3-1+3-1+……+(2n-1)-1に基づいて：
4. 買物カードのケース
5. 数当てゲームの設計
6. 10文字を含む文字列を作成する
7. 関数を記述する
8. アヒ ...
5月14日 00:38 投稿
AtCoder Beginner Contest 318 問題分析とC++解法
A - Full Moon (満月)
この問題は、N日目までの期間において、最初の満月がM日目に見え、その後P日ごとに満月が見える場合に、合計何回満月が見えるかを数えるものです。つまり、M, M+P, M+2P, ...という等差数列の項がN以下になるものがいくつあるかを求めます。
まず、N日目がM日目よりも前であれば、満月は一度も見えません。この場合、回数は0です。
N日目がM日目以降 ...
5月13日 23:06 投稿
部分文字列抽出と塗りつぶしアルゴリズムの実装
文字列包含範囲の抽出
与えられた文字列から、特定の部分文字列を全て含む最小の連続部分を抽出するアルゴリズム。左から右へ探索して部分文字列の最後の文字位置を特定し、次に右から左へ探索して部分文字列の最初の文字位置を特定することで最小範囲を決定する。
#include <iostream>
#include <string>
using namespace std;
void extractMinimalSubstri ...
5月13日 08:50 投稿
C言語における文字列の左シフトおよび右シフトの実装と判断
問題説明
左シフトとは、文字列の先頭にある指定された数の文字を末尾に移動することです。
例えば、"ABCDEF"を2文字左シフトすると"BCDEFAB"となり、3文字左シフトすると"DEFABC"になります。
実装コード
void left_shift(char* str, int k)
{
int j = 0;
assert(str);
for (j = 0; j < k; j++)
{
char temp = *str;
int ...
5月12日 22:51 投稿
アルコール耐久力ゲーム - プログラミング問題解決
L1-019 先に倒れる者 (15点)拳遊びは古代中国の酒文化における興味深い要素の一つです。テーブルに座る二人が拳遊びを行う方法は、それぞれが口で一つの数字を叫び、同時に手で一つの数字を表現します。もし誰かが表現した数字が、二人が叫んだ数字の合計と等しければ、その人が負け、負けた人は一杯の酒を飲まされます。両者とも勝つか両者とも負ける場合は次のラウンドに ...
5月12日 16:14 投稿