C++로 해결하는 가장 긴 등차수열 부분 수열 문제

문제 개요

정수로 이루어진 배열 A가 주어졌을 때, A에서 가장 긴 등차수열(arithmetic sequence) 부분 수열의 길이를 반환해야 합니다. 배열 A의 부분 수열이란 0 <= i_1 < i_2 < ... < i_k <= A.length - 1 조건을 만족하는 A[i_1], A[i_2], ..., A[i_k] 형태의 리스트를 의미합니다. 그리고 수열 B에서 인접한 두 원소의 차이 B[i+1] - B[i]가 모두 동일한 값을 가질 때(0 <= i < B.length - 1), B를 등차수열이라고 정의합니다.

예를 들어 입력이 [9,4,7,2,10]이라면 출력은 3이 됩니다. 가장 긴 등차수열 부분 수열이 [4,7,10]이기 때문입니다.

해결 전략: 다이나믹 프로그래밍

이 문제는 다이나믹 프로그래밍(DP)과 해시 맵을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 "인덱스 i에서 공차 diff로 끝나는 등차수열의 최대 길이"를 dp[i][diff]에 저장하는 것입니다. 모든 인덱스 쌍 (j, i)에 대해 공차를 계산하고, 이전 상태의 값에 1을 더해 길이를 갱신합니다. 부분 수열의 최소 길이는 2이므로 ret은 2로 초기화합니다.

알고리즘 단계

1. 맵 dp를 생성하고, n := A의 크기, ret := 2로 초기화합니다.
2. i를 0부터 n-1까지 반복합니다.
   • j를 0부터 i-1까지 반복합니다.
     • diff := A[j] - A[i]로 공차를 계산합니다.
     • dp[i, diff] := 1 + dp[j, diff]로 상태를 갱신합니다.
     • ret := max(1 + dp[i, diff], ret)로 최댓값을 갱신합니다.
3. ret을 반환합니다.

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int longestArithSeqLength(vector<int>& A) {
      unordered_map <int, unordered_map <int, int> > dp;
      int n = A.size();
      int ret = 2;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < i; j++){
            int diff = A[j] - A[i];
            dp[i][diff] = 1 + dp[j][diff];
            ret = max(1 + dp[i][diff], ret);
         }
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {9,4,7,2,10};
   Solution ob;
   cout << (ob.longestArithSeqLength(v1));
}

입력

[9,4,7,2,10]

출력

3

복잡도 분석

시간 복잡도는 O(n²)입니다. 모든 인덱스 쌍 (j, i)을 한 번씩 확인하기 때문입니다. 공간 복잡도 역시 최악의 경우 O(n²)로, 각 인덱스마다 서로 다른 공차 값을 해시 맵에 저장할 수 있기 때문입니다. 브루트포스 방식으로 모든 부분 수열을 탐색하는 지수 시간 복잡도에 비해 상당히 효율적인 접근입니다.