[알고리즘] Two Pointer

치치·2025년 1월 15일

알고리즘C++

목록 보기

5/24

투 포인터

두 개의 포인터를 활용해서 배열의 요소를 효과적으로 탐색하는 알고리즘이다
-> 실제 포인터는 아님
-> 전체적인 흐름만 봤을때 end와 start를 이동시키면서 내가 찾고자 하는 값과 비교하여 해당 값이 몇개 있는지 찾는 것

투 포인터 구현

시작점과 끝나는 지점이 첫번째 원소를 가리키도록 한다 (값을 넣는 것이 아닌 start와 end변수는 인덱스로써 사용된다)
[현재 부분합 sum][찾고자 하는 값 m]
sum >= m -> start를 1 증가
sum < m -> end를 1 증가
sum == m -> count 증가

조건문을 탈출하는 break문은 무조건 end를 연산시키는 코드위에 있어야한다

-> break문의 조건은 end가 SIZE보다 커지거나 같아지면인데, 이 조건이 만족하지 않는 경우에 바로 종료되야 하기 때문에 end값을 증가시키는 코드보다 위에 있어야한다
-> 해당 조건문이 불일치 할 경우에만 아래 코드로 들어가서 sum < m인지 확인하고 실행

만약 sum < m와 end가 SIZE보다 더 크다는 조건을 만족하는 경우
-> break문이 더 아래에 있을 경우, sum < m조건문으로 먼저 들어가서 sum += array[end++]가 실행된다. 원래라면 end값이 SIZE보다 더 커져서 바로 중지되야만 함

#include <iostream>
#define SIZE 5
using namespace std;

void TwoPointer(int m)
{
	int start = 0;
	int end = 0;

	int sum = 0;
	int count = 0;

	int array[SIZE] = { 1,2,3,2,5 };

	while (start <= end)
	{
    	// 누적합 >= 원하는 값 : 누적합 - start하고 이동
		if (sum >= m)
		{
			sum -= array[start++];
		}
        // end의 위치가 SIZE를 넘어가면 탈출
		else if (end >= SIZE)
		{
			break;
		}
        // 누적합 < 원하는 값 : 누적합 + end하고 이동
		else if (sum < m)
		{
			sum += array[end++];
		}
       
        // 위 코드와 별개로 if문 작성 / 같으면 count++
		if (sum == m)
		{
			count++;
		}
	}

	cout << count;

}


int main()
{
#pragma region 투 포인터

	TwoPointer(5);

#pragma endregion
	return 0;
}

코드를 처음 짰을때, 조건문의 순서에 따라 결과값이 달라졌다
조건문의 순서에 따라 우선순위가 달라지기 때문에 조심하자...
현재 방법은
sum >= m 경우일 때 start값을 먼저 이동시키는 코드로 시작하였지만 조건문의 순서를 바꿀 경우, 각 조건이 먼저 처리되는 순서에 따라 start와 end 포인터가 다르게 조정된다

기존의 방식

배열의 요소가 1 2 3 2 5 일 경우 count값이 3으로 정상적이게 나온다
예를 들어, 위의 코드에서 마지막 부분을 보면 마지막 원소인 5가 sum 2 < m 5 상황이라 누적합에 5를 넣어줘야한다. 그럼 결과가 sum 7 > m 5가 된다
end가 탈출하는 상황이 먼저 오지 않기때문에, 마지막의 원소인 5까지 판별이 가능하다

-> 만약, break문이 조건문의 맨 위에 오게 될 경우 end가 SIZE 값과 같거나 커지자마자 바로 종료될 것. 그렇다면 마지막 원소인 5가 원하는 값m과 같아져도 결과값에는 포함되어 나오지 않게 된다!

// 누적합 >= 원하는 값 : 누적합 - start하고 이동
		if (sum >= m)
		{
			sum -= array[start++];
		}
        // end의 위치가 SIZE를 넘어가면 탈출
		else if (end >= SIZE)
		{
			break;
		}
        // 누적합 < 원하는 값 : 누적합 + end하고 이동
		else if (sum < m)
		{
			sum += array[end++];
		}
       
        // 위 코드와 별개로 if문 작성 / 같으면 count++
		if (sum == m)
		{
			count++;
		}

잘못된 방식

break문이 제일 위에 있으면 안된다
start를 증가시키는 코드가 맨 위에 작성되어있어야 한다
-> 이유: end가 마지막 SIZE값을 넘어갔을 때, break 조건이 가장 위에 있으면 이 시점에서 함수가 종료된다
-> sum >= m 조건을 break문보다 앞에 두게 되면 end가 SIZE를 넘어간 상황이어도 sum >= m을 충족하게 되면 start값의 위치를 옮길 수 있다

배열의 요소가 1 2 3 2 5 일 경우 count값이 2로, 마지막 요소인 5의 count가 증가되지 않는다
종료되는 break문이 가장 위에 있기때문에 마지막 원소의 판별을 하기도 전에, end가 SIZE 값을 넘어버려서 바로 함수가 종료되어 버린다

while (start <= end)
{
	if (end >= SIZE)
	{
		break;
	}
	else if (sum >= m)
	{
		sum -= array[start++];
	}
	else if (sum < m)
	{
		sum += array[end++];
	}
	if (sum == m)
	{
		count++;
	}
}