문제 개요
수열 X₁, X₂, ..., Xn이 다음 조건을 모두 만족할 때, 이를 '피보나치 유사(fibonacci-like) 수열'이라고 정의합니다.
- n ≥ 3
- i + 2 ≤ n인 모든 i에 대해 Xi + Xi+1 = Xi+2
양의 정수로 구성되어 있고 값이 엄격하게 증가하는 배열 A가 주어졌을 때, A에서 가장 긴 피보나치 유사 부분수열(subsequence)의 길이를 찾아야 합니다. 해당하는 부분수열이 존재하지 않으면 0을 반환합니다.
예를 들어 입력이 [1, 2, 3, 4, 5, 6, 7, 8]이라면 결과는 5입니다. 이때 가장 긴 피보나치 유사 부분수열은 [1, 2, 3, 5, 8]입니다.
알고리즘 설계
이 문제는 해시 맵과 동적 계획법(DP)을 결합하면 효율적으로 해결할 수 있습니다. dp[i][j]를 "마지막 두 요소가 각각 A[j], A[i]인 피보나치 유사 부분수열의 최대 길이"로 정의하고, 다음 단계를 따릅니다.
- 결과 변수 ret := 0으로 초기화합니다.
- 값 → 인덱스 매핑을 저장할 맵 m을 생성하고, n := 배열 A의 크기로 설정합니다.
- n × n 크기의 DP 테이블 dp를 생성합니다.
- i를 0부터 n − 1까지 순회하며 m[A[i]] := i를 저장합니다.
- j를 i − 1부터 0까지 역방향으로 순회하며 다음을 수행합니다.
- req := A[i] − A[j]
- A[i] − A[j] < A[j]이면서 맵 m에 A[i] − A[j]가 존재하면: dp[i][j] := max(dp[i][j], dp[j][m[A[i] − A[j]]] + 1)
- 그 외의 경우: dp[i][j] := max(dp[i][j], 2)
- ret := max(ret, dp[i][j])
- 최종적으로 ret이 3 이상이면 ret을 반환하고, 그렇지 않으면 0을 반환합니다.
동작 원리 이해하기
배열 A가 엄격하게 증가하므로, 세 연속 항 (A[i] − A[j], A[j], A[i])이 성립하려면 이전 항 A[i] − A[j]가 반드시 A[j]보다 작아야 합니다. 맵을 사용하면 이전 항의 인덱스를 O(1) 시간에 찾을 수 있고, 이미 계산된 dp 값에 1을 더해 체인을 계속 확장해 나갈 수 있습니다. 유효한 세 항이 시작되지 않는 위치에는 기본값 2를 저장하여 두 항까지의 후보를 표현합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lenLongestFibSubseq(vector<int> & A) {
int ret = 0;
unordered_map <int, int> m;
int n = A.size();
vector < vector <int> > dp(n, vector <int>(n));
for(int i = 0; i < n; i++){
m[A[i]] = i;
for(int j = i - 1; j >= 0; j--){
int req = A[i] - A[j];
if(A[i] - A[j] < A[j] && m.count(A[i] - A[j])){
dp[i][j] = max(dp[i][j], dp[j][m[A[i] - A[j]]] + 1);
}else{
dp[i][j] = max(dp[i][j], 2);
}
ret = max(ret, dp[i][j]);
}
}
return ret >= 3 ? ret : 0;
}
};
main(){
vector<int> v = {1,2,3,4,5,6,7,8};
Solution ob;
cout << (ob.lenLongestFibSubseq(v));
}입력
[1,2,3,4,5,6,7,8]
출력
5
시간 및 공간 복잡도
모든 인덱스 쌍 (i, j)에 대해 맵 조회와 DP 갱신이 상수 시간 안에 이루어지므로, 전체 시간 복잡도는 O(n²)입니다. 공간 복잡도는 DP 테이블 저장을 위해 역시 O(n²)입니다.