アルゴリズムの考え方

文法を覚えているかだけでなく、問題文から必要な処理を組み立てられるかが重要です。

よくある問題と解法

累積和

N個の数列について、先頭からの合計を配列に保存すると、区間の合計を素早く求められます。

int[] values = { 2, 4, 1, 5 };
int[] prefix = new int[values.Length + 1];

for (int i = 0; i < values.Length; i++)
{
    prefix[i + 1] = prefix[i] + values[i];
}

// 0-indexedで [left, right) の合計
int left = 1;
int right = 3;
Console.WriteLine(prefix[right] - prefix[left]); // 5

前処理はO(N)、各区間の合計はO(1)で求められます。

発展

ソート、頻度カウント、貪欲法、幅優先探索・深さ優先探索などへ進みます。大切なのはアルゴリズム名を暗記することではなく、制約に合う解法を選び、その理由を説明できることです。

標準ライブラリを使えば常に最速、というわけではありません。データ量・制約・前提条件を確認し、計算量を理解しましょう。