[알고리즘] 투 포인터와 슬라이딩 윈도우

[투 포인터]

 

고정된 크기의 배열에 대해, 배열에 접근할 수 있는 포인터 두 가지(Left, Right)를 활용하여 탐색하는 방법이다. 보통 정렬된 상태의 연속 수열의 부분 합을 구할 때 많이 활용한다.

int TwoPointer(vector<int> _Arr, int _Value)
{
    int Result = 0;
    int Left = 0, Right = 0;
    int Sum = _Arr[0];
    int Size = _Arr.size();

    vector<int> answer;

    while (Left < Size && Right < Size)
    {
        if (Sum < _Value)
        {
            ++Right;
            if (Right < Size)
                Sum += _Arr[Right];
        }
        else if (Sum > _Value)
        {
            Sum -= _Arr[Left];
            ++Left;
        }
        else // Sum == _Value
        {
            if (/*특정 동작을 위한 if문*/)
            {
                // TODO
                ++Result;
            }

            // Sum == _Value인 경우에도 줄여서 다음 가능성 탐색
            // 없으면 그냥 break;
            Sum -= _Arr[Left];
            ++Left;
        }
    }

    return Result;
}

 

 

[슬라이딩 윈도우]

 

두 개의 포인터가 유동적으로 변하는 투 포인터와 달리, 슬라이딩 윈도우는 고정된 크기의 공간에 대한 탐색을 실시한다. 

int SlidingWindow(vector<int> _Arr, int _Value, int _WindowSize)
{
    int Result = 0;
    int Sum = 0;

    // 초기 윈도우 계산
    for (int i = 0; i < _WindowSize; ++i)
    {
        Sum += _Arr[i];
    }

    if (Sum == _Value)
    {
        ++Result;
    }

    // 오른쪽으로 윈도우 이동
    for (int i = _WindowSize; i < _Arr.size(); ++i)
    {
        Sum -= _Arr[i - _WindowSize]; // 왼쪽 끝 제거
        Sum += _Arr[i];                      // 오른쪽 새 값 추가

        if (Sum == _Value)
        {
            ++Result;
        }
    }

    return Result;
}