Python으로 리스트에서 가장 긴 교대 부분 수열의 길이 찾는 방법

숫자로 이루어진 리스트 nums가 주어졌을 때, 인접한 두 숫자의 차이가 양수와 음수를 번갈아 가며 나타나는 가장 긴 부분 수열(subsequence)의 길이를 찾는 문제를 살펴보겠습니다. 단, 첫 번째 차이는 양수여도 되고 음수여도 됩니다.

문제 이해하기

예를 들어 입력이 nums = [6, 10, 4, 2, 3, 9, 4, 7]이라면 정답은 6입니다. 그 이유는 [6, 10, 2, 9, 4, 7]이라는 부분 수열을 선택할 수 있고, 이때의 차이 값들이 [4, -8, 7, -5, 3]처럼 양수와 음수가 번갈아 나타나기 때문입니다.

풀이 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심은 각 인덱스마다 두 가지 상태를 함께 관리하는 것입니다.

• dp[i][0]: i번째 요소로 끝나고, 마지막 차이가 양수(증가)인 교대 부분 수열의 최대 길이
• dp[i][1]: i번째 요소로 끝나고, 마지막 차이가 음수(감소)인 교대 부분 수열의 최대 길이

구체적인 알고리즘 단계는 다음과 같습니다.

• n := nums의 크기
• dp := n×2 크기의 리스트를 생성하고 모든 값을 1로 초기화
• ans := 0
• i를 0부터 n-1까지 반복:
  • j를 0부터 i-1까지 반복:
    • nums[j] < nums[i]인 경우: dp[i][0] = max(dp[i][0], dp[j][1] + 1)
    • nums[j] > nums[i]인 경우: dp[i][1] = max(dp[i][1], dp[j][0] + 1)
  • ans = max(ans, dp[i][0], dp[i][1])
• ans 반환

Python 구현 예제

다음 코드를 통해 더 자세히 이해해 보겠습니다.

class Solution:
    def solve(self, nums):
        n = len(nums)
        dp = [[1] * 2 for _ in range(n)]
        ans = 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1)
                elif nums[j] > nums[i]:
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1)
            ans = max(ans, dp[i][0], dp[i][1])
        return ans

ob = Solution()
nums = [6, 10, 4, 2, 3, 9, 4, 7]
print(ob.solve(nums))

입력

[6, 10, 4, 2, 3, 9, 4, 7]

출력

6

복잡도 분석

이 알고리즘은 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이며, dp 배열 저장을 위해 공간 복잡도는 O(n)입니다. 참고로 이 문제는 각 지점에서 증가/감소 방향 전환 횟수만 세는 O(n) 최적화 풀이도 존재하지만, 위의 DP 접근 방식이 원리를 이해하기에는 가장 직관적입니다.