📒 갈무리 - 슬라이딩(Sliding)

📌 슬라이딩이란?

- 일정 범위가 이동하면서 범위 내에 있는 데이터를 이용해 문제를 해결하는 알고리즘

- 교집합의 정보를 공유하고 특정 부분만 변경하며 문제를 해결한다.

- 일정 범위의 값을 비교할 때 유용하게 사용한다.

- 주로 투 포인터와 함께 쓰인다.

📌 EX) Find Pivot Index

- INPUT의 값에서 하나의 피봇을 기준으로 왼쪽 범위의 array와 오른쪽 범위의 array의 합이 값이 같으면 피봇의 인덱스를 반환하고, 피봇이 되는 값이 없다면 -1을 반환하라.

// C++
#include <iostream>

using std::cout;
using std::endl;

// Test Input
const int INPUT[7] = { 1, 8, 2, 9, 2, 3, 6 };
//const int INPUT[7] = { 1, 1, 1, 1, 1, 3, 6 };
//const int INPUT[3] = { 2,5,7 };

const int SIZE = sizeof(INPUT) / sizeof(int);

int sumInput()
{
	int sum = 0;
	for (int i = 0; i < SIZE; ++i)
	{
		sum += INPUT[i];
	}
	return sum;
}

int findPivotIndex()
{
	int leftValue = 0;
	int rightValue = sumInput();
	int pastPivotValue = 0;

	for (int i = 0; i < SIZE; ++i)
	{
		int pivotValue = INPUT[i];
		leftValue += pastPivotValue;
		rightValue -= pivotValue;
		pastPivotValue = pivotValue;
        
		if (leftValue == rightValue)
		{
			return i;
		}
	}
	return -1;
}

int main()
{
	cout << findPivotIndex() << endl;
}

Output:
3

- rightValue를 INPUT 요소들의 합으로 초기화

- rightValue의 범위를 기준으로 rightValue와leftValue, pivotValue, pastPivotValue의 값을 변경해 가며 문제를 해결한다.