투 포인터 알고리즘(Two-Pointers Algorithm) | 슬라이딩 윈도우 알고리즘(Sliding Window)

투 포인터 알고리즘(Two-Pointers Algorithm)이란?

투 포인터 알고리즘은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻한다.

ㅤ

1차원 배열 위에 2개의 포인터를 만드는 경우

2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동

2개의 포인터가 양 끝에서 서로를 향해 이동

다음의 키워드가 등장하면 투 포인터 접근을 시도해 볼 가치가 있다.

• 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"

• 곱의 최소

코드

배열의 첫번째 원소와 배열의 마지막 원소에서 시작하는 경우

private static boolean isPairSum(int[] n, int x) {

	int left = 0;
	int right = n.length - 1;
	while (left < right) {
		if (n[left] + n[right] == x)
			return true;
		else if (n[left] + n[right] > x)
			right--;
		else
			left++;
	}
	return false;
    
}

둘 다 첫번째 원소에서 시작하는 경우

  long sum = 0;
  int start = 0;
  int end = 0;
  long result = 0;
  
    while (start < N) {
        if (sum > M || end == N) {
            sum -= arr[start];
            start++;
        } else {
            sum += arr[end];
            end++;
        }
        if (sum == M)
            result++;
    }
    
	System.out.println(result);
    

ㅤ

슬라이딩 윈도우 알고리즘(Sliding Window)이란?

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말합니다.
ㅤ
교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법입니다.
ㅤ
배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 매우 유용합니다.
투 포인터(two poitners) 알고리즘과 연동하여 많이 쓰입니다.
ㅤ
슬라이딩 윈도우 알고리즘은 사용 조건에 맞으면 연산 시간 단축에 매우 효과적이다.

위 이미지를 참고하여 보면, 투 포인트 알고리즘은 구간의 넓이가 조건에 따라 유동적으로 변하며, 슬라이딩 윈도우 알고리즘은 항상 구간의 넓이가 고정되어 있다는 차이점이 있습니다.