C++로 해결하는 흔들리는 부분 수열(Wiggle Subsequence) 문제

흔들리는 수열(Wiggle Sequence)이란?

연속된 숫자 사이의 차이가 양수와 음수를 엄격하게 번갈아 나타내는 수열을 흔들리는 수열(Wiggle Sequence)이라고 합니다. 이때 첫 번째 차이는 양수 또는 음수 어느 쪽이든 상관없습니다. 또한 원소가 두 개 미만인 수열은 자명하게 흔들리는 수열로 간주됩니다.

예를 들어 [1,7,4,9,2,5]는 인접한 숫자 간의 차이가 (6,-3,5,-7,3)으로 양수와 음수가 번갈아 나타나므로 흔들리는 수열입니다. 반면 [1,4,7,2,5]는 처음 두 차이가 모두 양수이고, [1,7,4,5,5]는 마지막 차이가 0이기 때문에 흔들리는 수열에 해당하지 않습니다.

문제 정의

정수로 이루어진 수열이 주어졌을 때, 흔들리는 수열의 조건을 만족하는 가장 긴 부분 수열(subsequence)의 길이를 구하는 것이 목표입니다. 여기서 부분 수열이란 원래 수열에서 일부 원소(0개일 수도 있음)를 삭제하고 남은 원소들의 원래 순서를 유지한 것을 의미합니다.

예를 들어 입력이 [1,7,4,9,2,5]라면, 전체 수열 자체가 이미 흔들리는 수열이므로 출력은 6이 됩니다.

해결 접근 방법

이 문제는 그리디(Greedy) 방식의 동적 계획법 아이디어로 효율적으로 해결할 수 있습니다. 핵심은 다음과 같습니다:

n := nums 배열의 크기
n이 0이면 0을 반환
up := 1, down := 1로 초기화
(up: 마지막 차이가 양수인 가장 긴 흔들리는 부분 수열의 길이, down: 마지막 차이가 음수인 경우의 길이)
i를 1부터 n-1까지 반복하며:
- nums[i] > nums[i-1]이면 up := down + 1
- nums[i] < nums[i-1]이면 down := up + 1
up과 down 중 최댓값을 반환

이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.

C++ 구현 예시

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 0;
        int up = 1;
        int down = 1;
        for(int i = 1; i < n; i++){
            if(nums[i] > nums[i - 1]){
                up = down + 1;
            }
            else if(nums[i] < nums[i - 1]){
                down = up + 1;
            }
        }
        return max(up, down);
    }
};
main(){
    Solution ob;
    vector<int> v = {1,7,4,9,2,5};
    cout << (ob.wiggleMaxLength(v));
}

입력

[1,7,4,9,2,5]