JavaScript로 배열에서 가장 긴 피보나치 부분 수열 찾기

피보나치 수열이란?

수열 X₁, X₂, ..., Xₙ이 다음 두 조건을 만족할 때 이를 피보나치 수열이라고 합니다.

n ≥ 3 (수열의 길이가 최소 3 이상)
모든 i + 2 ≤ n에 대해 Xᵢ + Xᵢ₊₁ = Xᵢ₊₂ (연속된 두 항의 합이 다음 항과 같음)

문제 정의

숫자 배열 arr을 첫 번째이자 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열 내에서 존재하는 가장 긴 피보나치 부분 수열의 길이를 찾아 반환해야 합니다.

여기서 부분 수열(subsequence)이란 원본 배열 arr에서 임의 개수의 요소(0개 포함)를 삭제한 후, 남은 요소들의 상대적인 순서는 그대로 유지하여 얻은 수열을 의미합니다.

입력 및 출력 예시

함수 입력이 다음과 같다고 가정해 보겠습니다.

입력:

const arr = [1, 3, 7, 11, 14, 25, 39];

출력:

const output = 5;

출력 설명:

배열에서 가장 긴 피보나치 부분 수열은 [3, 11, 14, 25, 39]이며, 각 항이 앞의 두 항의 합(3 + 11 = 14, 11 + 14 = 25, 14 + 25 = 39)을 만족하기 때문에 길이는 5가 됩니다.

접근 방법: 동적 계획법(DP) 활용

이 문제는 해시맵과 2차원 메모이제이션(memoization) 테이블을 결합한 동적 계획법으로 효율적으로 해결할 수 있습니다.

먼저 각 숫자 값이 배열에서 어느 인덱스에 위치하는지 저장하는 맵(map)을 생성합니다.
memo[i][j]는 arr[i]와 arr[j]를 마지막 두 항으로 하는 피보나치 부분 수열의 길이를 저장합니다.
모든 쌍 (i, j)에 대해 b - a(즉, arr[j] - arr[i])가 배열에 존재하고 그 인덱스가 i보다 작다면, 기존 피보나치 수열을 한 단계 확장할 수 있습니다.

코드 구현

const arr = [1, 3, 7, 11, 14, 25, 39];
const longestFibonacci = (arr = []) => {
    // 각 숫자의 인덱스를 저장하는 맵 생성
    const map = arr.reduce((acc, num, index) => {
        acc[num] = index;
        return acc;
    }, {});
    // 2차원 메모이제이션 테이블 초기화
    const memo = arr.map(() => arr.map(() => 0));
    let max = 0;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            const a = arr[i];
            const b = arr[j];
            // b - a가 존재하는지 확인
            const index = map[b - a];
            if (index < i) {
                memo[i][j] = memo[index][i] + 1;
            }
            max = Math.max(max, memo[i][j]);
        }
    }
    return max > 0 ? max + 2 : 0;
};
console.log(longestFibonacci(arr));

실행 결과

코드 설명

맵 생성: reduce를 사용해 각 숫자 값을 키로, 해당 인덱스를 값으로 하는 객체를 만듭니다. 이를 통해 O(1) 시간에 특정 값의 존재 여부와 위치를 확인할 수 있습니다.
메모 테이블: memo[i][j]는 arr[j]와 arr[i]를 연속된 두 항으로 가질 때의 피보나치 수열 길이를 나타냅니다.
점화식: b - a가 배열에 존재하고 그 인덱스가 i보다 작으면, memo[i][j] = memo[index][i] + 1로 이전 수열을 확장합니다.
최종 반환: 최대값에 처음 두 항(+2)을 더해 전체 길이를 계산합니다. 피보나치 수열이 존재하지 않으면 0을 반환합니다.

복잡도 분석

시간 복잡도: O(n²) — 모든 쌍 (i, j)를 한 번씩 순회합니다.
공간 복잡도: O(n²) — 2차원 메모이제이션 테이블을 사용합니다.