非IT職でもわかる基本情報技術者試験

応用情報 午後 問3「最長共通部分列の長さを求めるアルゴリズム」に出てくる用語（令和7年度 秋期）

結論

令和7年度 秋期 応用情報技術者試験 午後 問3（プログラミング）に出てくる用語を、1行の説明と解説ページへのリンクで並べたページ。問題文そのものは載せていません。

このページの使い方

令和7年度 秋期 応用情報技術者試験 午後 問3「二つの列の最長共通部分列（Longest Common Subsequence）の長さを求めるアルゴリズム」（出題分野：プログラミング）

著作権はIPA（情報処理推進機構）に帰属します。問題文と解答例は、IPAが公開しているものを参照してください。 このページでは問題文を引用せず、出てくる用語を並べるだけにしています。

この問題に解答群はありません。数値や字句を自分で書く形です。ここでは、問題文を読むのに要る言葉を並べます。

列についての言葉

用語1行の説明
部分列元の列から、順序を保ったままいくつか抜き出した列。抜いた要素は飛ばしてよい
共通部分列2つの列のどちらの部分列にもなっている列
最長共通部分列（LCS）共通部分列のうち、いちばん長いもの。複数あることもあるが、長さは1つに決まる

「部分列」と「部分文字列」は別物です。 部分文字列は連続した一続きを指しますが、部分列は飛び飛びでかまいません。ここを取り違えると、例の数え方が合わなくなります。

解き方についての言葉

用語1行の説明
再帰ある問題を、同じ形の小さな問題に置きかえて解く書き方。自分自身を呼び出す
動的計画法小さな問題の答えを表に記録しておき、同じ計算を繰り返さないやり方
時間計算量入力の大きさに対して、処理の手数がどう増えるかの見積り。O（オー）記法で書く
二次元配列行と列で位置を指す入れ物。動的計画法の表はこの形で持つ

この問題の骨はここです。 再帰のままだと同じ計算を何度も行うので、表に書き留めて繰り返しを避けます。表の大きさがそのまま手数になるため、時間計算量は2つの列の長さの積に比例します。

擬似言語についての言葉

用語1行の説明
擬似言語試験で使う、特定の言語によらない書き方。冊子の先頭に記述形式の一覧が付いている
for／while繰り返しを表す。forは回数が決まっている形、whileは条件が真のあいだ続く形
if／elseif／else条件で枝分かれする形。上から順に条件を見て、最初に真になったものを実行する

擬似言語の記述形式は、問題冊子の最初に必ず載っています。 覚えていなくても、その場で確かめられます。

混ざりやすいところ

迷う組分かれ目
部分列 と 部分文字列飛び飛びでよいか、連続していなければならないか
再帰 と 動的計画法同じ計算を繰り返すか、表に記録して繰り返さないか
最長共通部分列 と その長さ列そのものは複数あり得るが、長さは1つに決まる

問題文と解答例

このページでは問題文を引用していません。問題冊子・解答例・採点講評は、IPAのページで公開されています。

→ 問題冊子・配点割合・解答例・採点講評（2025年度、令和7年度）｜IPA

この記事に出てきた用語