Python으로 리스트에서 가장 긴 등차 부분 수열의 길이 구하는 프로그램

숫자로 이루어진 리스트 nums가 있다고 가정해 보겠습니다. 이때 우리가 구해야 하는 것은 이 리스트에서 만들 수 있는 가장 긴 산술(등차) 부분 시퀀스의 길이입니다.

여기서 산술 수열이란 인접한 두 원소의 차이가 항상 일정한 수열을 의미합니다. 즉, 수열 S에 대해 모든 i(0 ≤ i < S의 길이 - 1)에 대해 S[i+1] - S[i]의 값이 동일하다면 그 수열은 산술 수열입니다.

예를 들어 입력이 nums = [1, 4, 7, 10, 13, 20, 16]이라면 출력은 6이 됩니다. 부분 시퀀스 [1, 4, 7, 10, 13, 16]에서 인접한 원소 사이의 차이가 모두 3으로 일정하기 때문입니다.

문제 해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치 i와 공차 diff를 키로 하는 dp 테이블을 만들고, dp[i, diff]에 '공차가 diff인 산술 부분 시퀀스가 i에서 끝날 때의 최대 길이'를 저장하는 것입니다. 알고리즘의 단계는 다음과 같습니다.

• n := 배열 arr의 크기
• n <= 1이면 n을 그대로 반환
• res := 0 (최종 결과값)
• dp := 빈 맵(defaultdict), 키가 존재하지 않으면 기본값 1을 반환하도록 설정
• i를 1부터 n-1까지 반복:
  • j를 0부터 i-1까지 반복:
    • diff := arr[i] - arr[j]
    • dp[i, diff] := dp[j, diff] + 1
    • res := res와 dp[i, diff] 중 최대값
• res 반환

Python 예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

from collections import defaultdict
class Solution:
   def solve(self, arr):
      n = len(arr)
      if n <= 1:
         return n
      res = 0
      dp = defaultdict(lambda: 1)
      for i in range(1, n):
         for j in range(i):
            diff = arr[i] - arr[j]
            dp[i, diff] = dp[j, diff] + 1
            res = max(res, dp[i, diff])
      return res
ob = Solution()
nums = [1, 4, 7, 10, 13, 20, 16]
print(ob.solve(nums))

입력

[1, 4, 7, 10, 13, 20, 16]

출력

6

시간 및 공간 복잡도

모든 쌍 (i, j)를 한 번씩 확인하므로 시간 복잡도는 O(n²)입니다. 또한 각 위치별 공차 정보를 맵에 저장해야 하므로 공간 복잡도 역시 최악의 경우 O(n²)입니다. 완전 탐색으로 부분 시퀀스를 모두 검사하는 지수 시간 방식보다 훨씬 효율적인 접근 방법입니다.