[LeetCode] 873. Length of Longest Fibonacci Subsequence (Python)

Problem

 

Solution

dp
hash

• i, j를 피보나치 수열 마지막 두 숫자로 두고 dp[(i, j)] 에 해당 수열의 길이를 저장한다.
• 해시맵 index_map 을 사용하여 빠르게 arr[k] 의 index를 찾을 수 있도록한다.
• 해시셋을 이용하여 arr[i]+arr[j] in arr 여부를 확인한다.

Bruteforce 로 풀면 time limit exceeded 나는 문제. 

db를 사용해서 풀어햐한다.

 

(i, j)를 마지막 두 숫자로 하는 피보나치 수열 찾기!

• 즉, arr[i], arr[j]를 고정하고, arr[i] + arr[j] == arr[k]가 되는 k를 찾아가야 합니다.
• 이를 위해 j를 기준으로 i를 선택하고, (i, j) 쌍을 만들도록 설계합니다.

반복문을 돌때 j부터 돌아서 항상 i<j 가 보장되도록 순회해야한다. db(j,k) = 피보나치 수열의 길이

<dp.get((i, j), 2) + 1 의미>

• db[(i,j)] : (i, j) 를 마지막 두 숫자로하는 피보나치 부분 수열의 길이
• dp.get((i, j), 2) : dp 값이 없으면 2 사용 (기본값)
• +1 : 새로운 k를 추가했으므로 길이 증가 , 즉 db[(j, k)] = db[(i, j)] + 1

Code

- Brute Force: 1

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        answer = []
        if len(arr) == 3:
            if arr[0] + arr[1] != arr[2]:
                return 0

        for i in range(len(arr)):
            tmp = []
            tmp.append(arr[i])
            for j in range(i+1, len(arr)):
                tmp.append(arr[j])
                for x in range(j+1, len(arr)):
                    if tmp[-2] + tmp[-1] == arr[x]:
                        tmp.append(arr[x])
                #print(tmp)
                if len(answer) < len(tmp):
                    answer = tmp
                tmp = []
                tmp.append(arr[i])  

		#피보나치 수열 배열 길이가 2이고 [1, 1] 이 아니면 피보나치 만족x
        if len(answer) == 2:
            if answer[0] != 1 and answer[1] != 1:
                return 0
        return len(answer)

 

-Bruteforce : 2

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        max_len = 0

        for i in range(n):
            for j in range(i+1, n):
                a, b = arr[i], arr[j]
                length = 2

                while a+b in arr:
                    a, b = b, a+b
                    length += 1
                max_len = max(length, max_len)
        return max_len if max_len > 2 else 0

 

- dp

class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n = len(arr)
        max_len = 0
        index_map = {num: i for i, num in enumerate(arr)}
        dp = {}

        for j in range(len(arr)):
            for i in range(j):
                x, y = arr[i], arr[j]
                if x+y in index_map:
                    k = index_map[x+y] #next index
                    #기존 len+1
                    dp[(j, k)] = dp.get((i, j), 2) + 1  # 기존 길이 + 1
                    max_len = max(max_len, dp[(j, k)])
        return max_len if max_len >= 3 else 0
        
        return max_len if max_len > 2 else 0

 

 

Complexity

Time Complexity

 

• index_map 생성: O(N)
• 이중 루프 (i, j 탐색): O(N²)
• dp 딕셔너리 조회 (dp.get((i, j))) 및 업데이트: O(1)
• 총 O(N²) 

 

 

Space Complexity

 

• index_map: O(N)
• dp: O(N²)
• 기타 변수: O(1)
• 총 O(N²)