[LeetCode] 873. Length of Longest Fibonacci Subsequence

출처: https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/

Length of Longest Fibonacci Subsequence - LeetCode

문제

한 시퀀스 X1, X2, ..., Xn가 다음과 같다면 유사-피보나치이다.

• n >= 3
• 모든 i + 2 <= n에서 Xi + Xi+1 = Xi+2

강한(strictly) 증가 배열 arr이 주어지면, arr에서 가장 긴 유사-피보나치의 서브-시퀀스 길이를 반환하라. 없다면 0을 반환하라.

 

서브-시퀀스는 arr에서 원소 순서의 변화없이 원소의 삭제로 얻을 수 있는 arr을 말한다. 예를들어, [3, 5, 8]은 [3, 4, 5, 6, 7, 8]의 서브-시퀀스이다.

예제

nput: arr = [1,2,3,4,5,6,7,8]
Output: 5

Explanation: The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Input: arr = [1,3,7,11,12,14,18]
Output: 3

Explanation: The longest subsequence that is fibonacci-like: [1,11,12], [3,11,14] or [7,11,18].

풀이

브루트 포스하게 문제를 접근해보자.

 

문제에서 얘기한 것처럼 찾아야 하는 서브시퀀스 배열은 Xi + Xi+1 = Xi+2의 관계를 가져야 하므로, 서브시퀀스 배열의 시작인 0th 원소와 1th 원소가 어떤 값인지가 중요하다.

 

서브시퀀스 배열의 0th원소를 i, 1th원소를 j라고 할 때, 아래의 코드를 통해서 모든 서브 시퀀스의 배열을 찾을 수 있다.

const nums = new Set(arr);

N = arr.length
for (let i = 0; i < N-1; i++) {
    for (let j = i+1; j < N; j++) {
        const sub = [arr[i], arr[j]];
        let sub_index = 0;
        while ( nums.has(sub[sub_index]+sub[sub_index+1] ) {
            sub.push(sub[sub_index]+sub[sub_index+1]);
            sub_index += 1;
        }
        if (sub.length > 2) {
            ans = Math.max(ans, sub.length);
        }
    }
}

이 방법의 핵심은 i와 j(0th와 1th)의 모든 케이스를 확인하여 서브-시퀀스를 만드는 것이라 볼 수 있다.

 

브루트 포스한 방법에서 조금 더 최적화할 수 있는 방법을 생각하기 위해 아래의 예시를 살펴보자. arr = [1, 2, 4, 5, 7, 9, 14]일 때, 만들 수 있는 서브시퀀스 중 일부만 작성한 것이다.

arr = [1, 2, 4, 5, 7, 9, 14]

sub1 = [1, 4, 5, 9, 14]
sub2 = [4, 5, 9, 14]
sub3 = [5, 9, 14]

예시에서 보여준 3개의 서브-시퀀스의 관계를 표현하면 sub1 ⊃ sub2 ⊃ sub3이다. 이제 다음과 같은 질문은 해보자.

• sub3을 찾으려고 하고 하는데, sub2의 존재를 이미 알고 있다면
• sub3을 찾을 필요가 있는가?

답은 찾을 필요가 없을 것이다. 어떻게 최적화를 해야 할까? 탐색 결과에 어떤 포함관계가 존재하는 걸 보니...... 다이나믹 프로그래밍 방법으로 최적화할 수 있지 않을까?

 

다이나믹 프로그래밍을 이용하기 위해서는 현재 스텝의 값이 이전 스텝의 값과 어떤 관계가 존재해야 한다. 이 문제에서는 다음과 같은 관계를 생각해볼 수 있다.

• 서브 시퀀스(sub)의 마지막 인덱스가 last_i라고 할 때
• dp[i][j]: sub[last_i] = arr[j] 이고 sub[last_i-1] = arr[i]인 서브시퀀스의 최대 길이
• dp[j][k] = dp[i][j] + 1, (i < j < k)

코드로 작성해보면 아래와 같다.

const index = new Map();
arr.forEach((val, key) => index[val] = key)

const dp = new Array(arr.length).fill(0).map(val => new Array(arr.length).fill(0));

let ans = 0;
for (let k = 0; k < arr.length; k++) {
    for (let j = 0; j < k; j++) {
        let i = index[arr[k]-arr[j]] ?? -1;
        if (i >= 0 && i < j) {
            const cand = (dp[i][j] > 2 ? dp[i][j] : 2) + 1;
            dp[j][k] = cand;
            ans = Math.max(ans, cand);
        }
    }
 }

Github: 873.js

opwe37/Algorithm-Study