문제 개요
엄격하게 오름차순으로 정렬된 양의 정수 리스트 nums가 주어졌다고 가정해 봅시다. 이때 모든 i > 1에 대해 A[i] = A[i - 1] + A[i - 2] 조건을 만족하는 가장 긴 부분 수열 A(최소 길이 3)의 길이를 구해야 합니다.
예를 들어 입력이 nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]라면, [1, 2, 3, 5, 8, 13]을 선택할 수 있으므로 출력은 6이 됩니다.
해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
A := nums,n := A의 크기,maxLen := 0으로 초기화합니다.- 리스트 A의 모든 원소를 담은 집합 S를 생성합니다. 집합을 사용하면 특정 값의 존재 여부를 O(1) 시간에 확인할 수 있습니다.
- 모든 인덱스 쌍 (i, j)에 대해 두 원소를 피보나치 수열의 시작점으로 삼습니다.
- x := A[j], y := A[i] + A[j]로 설정하고, y가 집합 S에 존재하는 동안 다음을 반복합니다.
- z := x + y로 다음 항을 계산합니다.
- x := y, y := z로 값을 갱신합니다.
- length를 1 증가시키고, maxLen과 비교하여 더 큰 값을 저장합니다.
- 반복이 끝난 후 maxLen이 3 이상이면 maxLen을 반환하고, 그렇지 않으면 유효한 부분 수열이 없으므로 0을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n² × L)입니다. 여기서 L은 평균적인 피보나치 체인의 길이입니다. 집합 조회 덕분에 각 후보 수열을 효율적으로 확장할 수 있습니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution: def solve(self, nums): A = nums n = len(A) maxLen = 0 S = set(A) for i in range(0, n): for j in range(i + 1, n): x = A[j] y = A[i] + A[j] length = 2 while y in S: z = x + y x = y y = z length += 1 maxLen = max(maxLen, length) if maxLen > 2: return maxLen else: return 0 ob = Solution() nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] print(ob.solve(nums))
입력
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
출력
6
동작 설명
위 예제에서 알고리즘은 가능한 모든 시작 쌍을 검사합니다. 예를 들어 (1, 2)를 시작점으로 선택하면 1 + 2 = 3이 리스트에 존재하고, 이어서 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13까지 연속적으로 발견됩니다. 따라서 부분 수열 [1, 2, 3, 5, 8, 13]의 길이인 6이 최종 결과로 반환됩니다.