슬라이딩 윈도우 / 투포인터

a·2023년 7월 6일

알고리즘

목록 보기

5/17

투 포인터와 슬리이딩 윈도우

이 두 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있습니다.

그렇다면 이 두 알고리즘의 차이점은 무엇일까요?

바로, 부분 배열 길이의 변화 여부입니다.

더 쉽게 말해서, 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만 슬리이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적입니다.

슬라이딩 윈도우

슬라이딩 윈도우 기법은 배열에서 연속된(정렬된) 부분 배열의 최대 합을 효율적으로 구하는 방법 중 하나입니다. 이 기법은 고정된 크기의 윈도우를 배열에서 이동하면서 부분 배열의 합을 계산하고, 최대 합을 찾는 방식으로 동작합니다.

주어진 문제가 부분 배열의 합을 구하는 것이라 할 때, 오른쪽으로 한 칸 옮기더라도 옮기기 전 부분 배열과 옮기고 난 후에는 겹치는 부분이 존재합니다. 즉, 기존 구간에서 빠지게 되는 가장 왼쪽 칸의 값은 삭제하고 새 구간에 포함되는 값을 추가하는 방식입니다.

예시

public class SlidingWindowExample {
    public static int findMaxSum(int[] nums, int k) {
        int maxSum = Integer.MIN_VALUE;
        int currentSum = 0;
        
        // 윈도우의 시작과 끝 인덱스
        int start = 0;
        int end = 0;
        
        while (end < nums.length) {
            // 현재 윈도우의 합을 계산
            currentSum += nums[end];
            
            // 윈도우의 크기가 k가 되면 최대 합을 갱신하고 시작 인덱스를 증가시킴
            if (end - start + 1 == k) {
                maxSum = Math.max(maxSum, currentSum);
                currentSum -= nums[start];
                start++;
            }
            
            end++;
        }
        
        return maxSum;
    }
}

투포인터

투 포인터 알고리즘(Two Pointers Algorithm)은 배열이나 리스트를 순회하면서 두 개의 포인터를 사용하여 원하는 조건을 만족하는 부분 배열이나 부분 리스트를 찾는 데 사용되는 효율적인 알고리즘입니다. 주로 배열이 정렬되어 있는 경우에 사용되며, 두 개의 포인터를 이용해 배열을 순회하면서 원하는 조건을 만족하는 부분 배열을 찾는야하기 때문에 슬라이딩 윈도우랑 달리 가변적인 크기의 배열에서 찾는 방식으로 작동합니다.

이미지출처
투 포인터 알고리즘에서는 대게 두 개의 유형이 존재합니다.

2개의 포인터 변수 시작점이 배열의 시작점인 경우(같은 진행방향)
정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우(반대 진행방향)

반대 진행방향 예시

N개의 정수를 가진 정렬된 배열 A가 있을 때 두 원소의 합이 X인 경우가 있는지에 대해 확인

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;
}

같은 진행방향 예시

n개의 정수를 가진 배열 A가 있을 때 배열에서 i,j까지 원소의 합이 m이 되는 경우의 수

public static long findCountBySumSimilar(int[] arr, int M) {
    int N = arr.length;
    long sum = 0;
    int start = 0;
    // end 포인터를 while 루프 조건에서 증가시키기 때문에 0으로 초기화
    int end = 0; 
    long result = 0;

    // 윈도우의 끝(end)이 배열 끝에 도달하기 전까지 반복
    while (end < N) {
        
        // 1. 윈도우 확장: 일단 end의 원소를 더하고 end를 증가시킴 (고정 윈도우의 기본 흐름)
        sum += arr[end];

        // 2. 윈도우 처리 및 축소: sum이 목표 M을 초과하면 start를 증가시켜 윈도우 축소
        // 이 부분이 고정 윈도우의 'K에 도달하면 start++' 로직과 형태상 유사
        while (sum > M) {
            // sum이 M을 초과했으므로 start의 원소를 빼고 start를 이동
            sum -= arr[start];
            start++;
        }
        
        // 3. 조건 검사: 윈도우 확장 또는 축소 후에 조건(sum == M)이 만족하는지 확인
        // 주의: 이 조건 검사는 end를 확장한 직후 또는 start를 움직인 직후에 수행됨
        if (sum == M) {
            result++;
        }
        
        // 다음 반복을 위해 end 포인터를 이동 (루프의 끝에서 처리)
        end++;
    }

    return result;
}

참고 : https://hongjuzzang.github.io/cs/two_pointers/,
https://bbangson.tistory.com/72