はじめに

こんにちは、やっしです。
この記事はTechCommit AdventCalendar2023の14日目の記事です。

前回はhideさんによる記事「備忘録 storybook7系とvuetify3の連携方法」です。

概要

この記事では、プログラミングスキルを向上させるための素晴らしいコンテンツ「LeetCode」について紹介します。また、LeetCodeの実際の問題を1つ取り上げ、それを解くためのいくつかのアプローチを見ていきます。さらに、私が参加しているTechCommitコミュニティの「LeetCodeを解く会」の活動についてもご紹介します。

目次

LeetCodeとは何か
LeetCodeの問題例：「N-th Tribonacci Number」
「LeetCodeを解く会」の紹介
最後に：次の記事の紹介
参考資料

LeetCodeとは何か

LeetCodeでは、基本的なアルゴリズムの問題から、実際のテック企業の面接で出題されるような複雑な問題まで、幅広い難易度の問題が用意されています。ウェブ上で解答を提出することができるので、その場で答え合わせをすることができます。また、問題によってはコードの実行時間の制限時間がシビアなものもあり、ユーザーは解答の正しさだけではなく、計算量を小さくし制限時間内に収められるよう工夫する必要もあります。そのため、単に正しいアルゴリズムを導く練習もできますし、解けたらそのアルゴリズムの計算量を改善することに挑戦して楽しむこともできます。

LeetCodeの問題例：「N-th Tribonacci Number」

LeetCodeの問題の一例として、「N-th Tribonacci Number」という問題を紹介します。Tribonacci数列は、各項が直前の3つの項の和となる数列です。この問題では、与えられたnに対して、Tribonacci数列のn番目の値を求めることが目標です。

問題の説明

Tribonacci数列$T_n$は次のように定義されます：

\displaylines{T_0 = 0, T_1 = 1, T_2 = 1 \text{ and } \\ T_{n+3} = T_n + T{n+1} + T{n+2} \text{ for } n >= 0, n \in \mathbb{N}}

たとえば、$n = 4$の場合、$T_4 = 1 + 1 + 2 = 4$となります。

「与えられた0以上の整数nに対して、Tribonacci数列のn項目を求めなさい。」という問題です。

問題の原文

The Tribonacci sequence Tn is defined as follows:
T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.
Given n, return the value of Tn.

Example 1:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:
Input: n = 25
Output: 1389537

この問題の解法は、初心者から経験豊富なプログラマーまで、様々なアプローチが考えられます。

解法の紹介

ここでは、4つの異なるアプローチを紹介します。1つ目は単純な再帰に基づくもの、2つ目は1つ目を改良した線形反復再帰プロセスで構築したアルゴリズムによる解法、3つ目はメモ化を利用したもの、そして4つ目は数学の知識を活用した高速なアルゴリズムによる解法です。

単純な再帰による解法

初学者にとって理解しやすい単純な再帰的アプローチです。コードは直感的で、再帰の基本的な概念を学ぶのに適しています。ただし、計算量は$O(3^n)$と非効率で大きなnに対しては不適切です。

function tribonacci(n: number): number {
    if (n === 0) {
        return 0;
    } else if (n === 1 || n === 2) {
        return 1;
    } else {
        return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3);
    }
}

線形反復再帰プロセスによる解法

このアプローチは1つ目のアルゴリズムに「状態変数=counter」を追加して、再帰呼び出しの回数を削減したものです。1つ目と比較すると1回の再帰処理の中で自分自身を呼び出す回数は1回です。そのため計算量は$O(n)$となります。

/**
 * 線形反復再帰プロセスによる解き方
 */
function tribonacci(n: number): number {
    return tribIter(1, 1, 0, n);
};

function tribIter(a2: number, a1: number, a0: number, counter: number): number {
    if (counter === 0) {
        return a0;
    }

    return tribIter(a2 + a1 + a0, a2, a1, counter - 1);
}

メモ化を利用した解法

この方法では、再計算を避けるために過去の計算結果を保存します。直感的で分かりやすい上に、計算量は$O(n)$と効率的です。

function tribonacci(n: number): number {
    let sequence = [0, 1, 1];

    if (n in sequence) {
        return sequence[n];
    }

    for (let i = 3; i <= n; i++) {
        sequence.push(sequence[i - 1] + sequence[i - 2] + sequence[i - 3]);
    }

    return sequence[n];
}

行列を使った解法

最後に紹介するこのアプローチは、行列の累乗を利用して計算効率を大幅に向上させます。計算量は$O(\log n)$となります。

アルゴリズムの導出

Tribonacci 数列$T_n$に対して次が成り立ちます。

\begin{pmatrix}
T_{n+3} \\
T_{n+2} \\
T_{n+1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}
\begin{pmatrix}
T_{n+2} \\
T_{n+1} \\
T_n
\end{pmatrix}
\quad (\forall n \in \{0, 1, 2, \ldots \}).

右辺の3次正方行列をAと置きます。すなわち、

A = \begin{pmatrix}
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{pmatrix}

このとき、$T_n$は行列Aの累乗を使って下記のように表せます：

\begin{align}
T_n = \left\langle
\begin{pmatrix}
0 \\
0 \\
1
\end{pmatrix},
\begin{pmatrix}
T_{n+2} \\
T_{n+1} \\
T_n
\end{pmatrix}
\right\rangle

&= \left\langle
\begin{pmatrix}
0 \\
0 \\
1
\end{pmatrix},
A
\begin{pmatrix}
T_{n+1} \\
T_n \\
T_{n-1}
\end{pmatrix}
\right\rangle \\

&= \left\langle
\begin{pmatrix}
0 \\
0 \\
1
\end{pmatrix},
A^2
\begin{pmatrix}
T_n \\
T_{n-1} \\
T_{n-2}
\end{pmatrix}
\right\rangle \\

&= \dots \\

&= \left\langle
\begin{pmatrix}
0 \\
0 \\
1
\end{pmatrix},
A^n
\begin{pmatrix}
1 \\
1 \\
0
\end{pmatrix}
\right\rangle
\end{align}

\text{ただし、} \left\langle, \right\rangle \text{は3次元ユークリッド空間の標準内積を表すものとする。}

よって

T_n = \left\langle
\begin{pmatrix}
0 \\
0 \\
1
\end{pmatrix},
A^n
\begin{pmatrix}
1 \\
1 \\
0
\end{pmatrix}
\right\rangle

\quad (\forall n \in \mathbb{N}, n \geq 3).

この結果から、Tribonacci数列の一般項$T_n$は、ベクトルに行列$A$の$n$乗を作用させた結果として得られることがわかる。

さて、このまま行列の場合で話を進める前に、ここで実数$a, b$に対して、$a^n b$を計算量$O(\log n)$で求めるアルゴリズムについて考察する。

まずはじめに$O(n)$のアルゴリズムを見てみよう。

const a = 3; // 任意の数値でOK
const b = 2; // 任意の数値でOK
/**
 * 計算量：O(n)
 */
function multiple(n: number): number {
    if (n === 0) {
        return b;
    }

    return a * multiple(n - 1);
}

次に、計算量$O(\log n)$のアルゴリズムについて考える。

/**
 * 計算量：O(log n)
 */
function multiple(n: number): number {
    return multipleIter(n, a, b);
}

function multipleIter(n: number, a: number, b: number) {
    if (n === 0) {
        return b;
    } else if (n % 2 === 0) {
        return multipleIter(n / 2, a * a, b);
    } else {
        return multipleIter(n - 1, a, a * b);
    }
}

注目すべきは、multipleIterのelse if (n % 2 === 0)のところだ。このアルゴリズムでは、nが奇数のときは$b$に$a$をかけて「被作用素を更新」して、nが偶数のときは$a$を累乗して「作用素を更新」することで計算回数を大幅に減らしている。

話を行列の場合に戻そう。「作用素」を行列$A$、「被作用素」を

\begin{pmatrix}
1 \\
1 \\
0
\end{pmatrix}

と捉えて、先ほどのmulipleIterと同じアナロジーを使えば下記のアルゴリズムを得る。（※SICP練習問題1.19も参考になります。）

function tribonacci(n: number): number {
    return fastTribIter(1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, n);
}

/**
 * tribonacci数列を1項進める変換（R^3→R^3）の表現行列をPとし、Pの第i,j成分をpijとする。
 *
 * @param a tribonacci数列の項
 * @param b tribonacci数列の項
 * @param c tribonacci数列の項
 * @param p11
 * @param p21
 * @param p31
 * @param p12
 * @param p22
 * @param p32
 * @param p13
 * @param p23
 * @param p33
 * @param count
 * @returns
 */
function fastTribIter(
    a: number,
    b: number,
    c: number,
    p11: number,
    p21: number,
    p31: number,
    p12: number,
    p22: number,
    p32: number,
    p13: number,
    p23: number,
    p33: number,
    count: number
): number {
    if (count === 0) {
        return c;
    } else if (count % 2 === 0) {
        // countが偶数の場合は表現行列を2乗する
        return fastTribIter(
            a,
            b,
            c,
            p11 * p11 + p21 * p12 + p31 * p13,
            p11 * p21 + p21 * p22 + p31 * p23,
            p11 * p31 + p21 * p32 + p31 * p33,
            p12 * p11 + p22 * p12 + p32 * p13,
            p12 * p21 + p22 * p22 + p32 * p23,
            p12 * p31 + p22 * p32 + p32 * p33,
            p13 * p11 + p23 * p12 + p33 * p13,
            p13 * p21 + p23 * p22 + p33 * p23,
            p13 * p31 + p23 * p32 + p33 * p33,
            count / 2
        );
    } else {
        // countが奇数の場合は表現行列をtribonacci数から成るベクトル（a, b, cを縦に並べてできる3次元の縦ベクトル）
        // にかけてベクトル（a,b,c）を更新する
        return fastTribIter(
            a * p11 + b * p12 + c * p13,
            a * p21 + b * p22 + c * p23,
            a * p31 + b * p32 + c * p33,
            p11,
            p21,
            p31,
            p12,
            p22,
            p32,
            p13,
            p23,
            p33,
            count - 1
        );
    }
}

「LeetCodeを解く会」の紹介

TechCommitでは、毎週金曜日の21:00〜22:00に「LeetCodeを解く会」が開催されています。メンバーは、指定されたLeetCodeの問題を事前に解いて、当日解答を共有し、アルゴリズムや解法について話し合います。この活動では学び合いと成長を重視しており、新しいメンバーを歓迎しています。
興味のある方はTechCommitまで！

最後に：次の記事の紹介

15日目の記事はMi Nさんです。お楽しみに！

参考資料