수열 X_1, X_2, ..., X_n이 다음 조건을 만족하면 피보나치 유사(fibonacci-like) 수열이라고 정의합니다.
n >= 3
모든 i + 2 <= n에 대해 X_i + X_i+1 = X_i+2 성립
엄격하게 증가하는 배열 A가 하나의 수열을 이룬다고 할 때, A에서 가장 긴 피보나치 유사 부분 수열의 길이를 구해야 합니다. 만약 그러한 수열이 존재하지 않는다면 0을 반환합니다.
예를 들어 입력이 A = [1,2,3,4,5,6,7,8]이라면 출력은 5가 됩니다. 이는 길이가 5인 수열 [1,2,3,5,8]이 존재하기 때문입니다.
해결 접근 방법
이 문제는 동적 계획법(DP)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 연속된 두 수 (a, b)로 끝나는 피보나치 유사 부분 수열의 길이를 맵에 저장하고, 배열을 뒤에서부터 순회하면서 값을 갱신하는 것입니다. 단계별 풀이 과정은 다음과 같습니다.
sA := A의 원소들로 구성한 집합(set)
last := A의 마지막 원소
B := A에 포함된 각 원소와 빈도수를 담은 맵(Counter)
best := 0
i를 A의 크기부터 0까지 역순으로 반복:
a := A[i]
A[i+1:] 부분 배열의 각 원소 b에 대해:
c := a + b
c가 sA에 존재하면:
B[a,b] := 1 + B[b,c]
best := best와 B[a,b]+2 중 더 큰 값
그렇지 않고 c > last이면:
내부 반복문 탈출
best 반환
예제 코드
다음 구현을 통해 더 자세히 이해해 보겠습니다.
from collections import Counter
def solve(A):
sA = set(A)
last = A[-1]
B = Counter()
best = 0
for i in reversed(range(len(A))):
a = A[i]
for b in A[i+1:]:
c = a+b
if c in sA:
B[a,b] = 1 + B[b,c]
best = max(best , B[a,b]+2)
elif c>last:
break
return best
A = [1,2,3,4,5,6,7,8]
print(solve(A))
입력
[1,2,3,4,5,6,7,8]
출력
5
복잡도 분석
위 알고리즘은 모든 (a, b) 쌍을 한 번씩 검사하므로 시간 복잡도는 O(n²)이며, 두 수 쌍을 키로 하는 DP 맵을 사용하기 때문에 공간 복잡도 역시 O(n²)입니다. 배열이 엄격하게 증가한다는 전제 덕분에 a + b가 배열의 최댓값(last)을 초과하는 순간 내부 반복문을 조기에 종료할 수 있어 실제 실행 시간을 크게 줄일 수 있습니다.