[Algorithm] 투 포인터와 슬라이딩 윈도우

투 포인터 (Two Pointers Algorithm)

투 포인터 알고리즘은 배열/리스트를 탐색하는 알고리즘 중 하나로, 배열에 두 개의 포인터를 두고 위치를 기록하며 계산을 처리합니다.

 

간단한 문제로 예시를 들어보겠습니다.

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

문제를 보면 배열의 연속된 원소의 합이 M이 되는 경우의 수를 구하라고 합니다.

이 문제는 대놓고 투 포인터를 사용하라고 나와있는 문제 중 하나입니다. 무지성으로 모든 경우를 탐색한다면 시간복잡도가 O(N^2)가 나오겠지만, N=10,000이기 때문에 그렇게 하면 문제의 시간 제한인 0.5초가 초과될 것입니다.

 

그럼 투 포인터를 사용해서 이 문제를 풀어보겠습니다.

먼저 left, right 2개의 포인터를 준비합니다. left는 부분 배열의 왼쪽 끝, right는 부분 배열의 오른쪽 끝을 가리키는 포인터입니다. 초기 단계는 left = right = 0이며 항상 left <= right 를 유지해야 합니다.

 

위 조건을 만족하면서 아래의 과정을 left < N일 동안 반복합니다.

- 현재 합이 M이상 또는 right == N이라면 left++, 아니라면 right++

- 현재 합이 M -> 정답개수++

 

이를 코드로 나타내면 다음과 같습니다.

import java.io.*;
import java.util.*;

public class boj_2003_수들의합2 {

    static int N, M, ans = 0;
    static int[] A = new int[10000];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        int left = 0, right = 0;
        int sum = 0;
        while (left < N) {
            if (sum >= M) {
                sum -= A[left++];
            } else if (right == N) {
                break;
            } else {
                sum += A[right++];
            }
            
            if (sum == M) {
                ans++;
            }
        }
        
        System.out.println(ans);
    }

}

 

투 포인터를 사용하게 되면 시간복잡도를 O(N)까지 줄일 수 있습니다. left와 right는 모두 1씩 증가하며 최대 N까지 증가할 수 있는데,

left <= right이므로 최대 N번 증가할 수 있기 때문이죠.

 

슬라이딩 윈도우 (Sliding Window)

투 포인터와 유사한 기법으로 슬라이딩 윈도우(Sliding Window)라는 기법도 존재합니다. 이 기법은 투 포인터와 같이 배열을 훑으며 지나간다는 공통점이 있지만, 투 포인터와 다르게 구간의 크기가 변하지 않고 일정하다는 차이점이 있습니다.

문제에서 제시하는 부분 배열의 크기가 일정한 경우, 슬라이딩 윈도우 기법을 사용하면 될 것 같습니다.

 

 

---

참고

https://m.blog.naver.com/PostView.naver?blogId=kks227&logNo=220795165570&navType=by