17. 투 포인터, 슬라이딩 윈도우 (1)

투 포인터와 슬라이딩 윈도우는 비교적 간단한 알고리즘이지만 강력한 알고리즘이기도 합니다. 직관적으로 보았을 때 O(N^2) 이상으로 해결해야하는 문제를 선형시간(O(N))으로 해결해주기 때문입니다. 투 포인터와 슬라이딩 윈도우가 완벽히 일치하는 알고리즘은 아니지만 설계적 측면에서 궤를 같이 한다고 할 수 있습니다.

투 포인터는 간단히 말해서 연속되는 value들을 이용하여 특정 목표에 맞는 값을 찾아주는 알고리즘이라고 할 수 있습니다. 여기서 주의해야할 것은 어디까지나 연속된 값들을 이용하여 풀어나가는 문제에 한정적으로 사용해야한다는 것입니다. 만일 주어진 값들의 연속성이 선행조건으로 주어지지 않는 경우에는 투 포인터를 사용할 수 없습니다. 그런 면에서 문제에서 주어진 값들을 그대로 활용해야하는 경우나 정렬을 통하여 연속성을 추가해줄 수 있는 경우에 사용할 수 있는 알고리즘이라고 할 수 있습니다.

투 포인터를 이용하여 문제를 풀이하는 방법은 간단합니다. 우선 정수로 이루어진 배열이 있다고 가정해봅시다. 그리고 그 정수들중 연속된 몇 개의 정수들의 합이 특정 값이 된다고 하였을 때 그 값을 만들 수 있는 조합은 몇 가지가 될 것이냐라는 문제가 있다고 해봅시다. 만일 투 포인터를 사용하지 않는다면 백트레킹 등을 이용하여 나올 수 있는 모든 케이스에 대해 탐색하는 것이 최선일 것입니다. 문제를 출제하는 사람은 투 포인터를 생각하고 문제를 출제하였을 것이기 때문에 필연적으로 시간 초과가 발생할 것입니다.

위와 같은 문제에 사용할 수 있는 것이 투 포인터입니다. 투 포인터는 우선 배열을 가르키는 두 개의 포인터를 만듭니다. 두 개의 포인터는 각각 배열에서 특정 위치를 지정해주는 시작점과 끝점이라고 할 수 있습니다.(여기서는 start pointer와 end pointer라고 부르겠습니다.) 그리고 그 포인터를 이동시켜가면서 우리가 원하는 값을 찾아주는 것입니다. 위 문제에서는 배열내 연속된 숫자들의 합을 이용하는 것이므로 더해가면서 값을 찾아주어야할 것입니다. 두 개의 포인터를 정수들을 더해주는 과정에서 움직이게 됩니다. 최초에는 어떠한 값도 합에 들어오지 않았기 때문에 end pointer를 이동시켜 첫 번째 값을 포함시킵니다. 이때 우리가 원하는 값이 나왔다면 답을 계산해줄 count 변수에 하나의 값을 더해주고 그렇지 않은 경우라면 조건에 따라 start pointer와 end pointer를 이동시켜줍니다. end pointer는 현재 포함된 값들의 합이 원하는 값보다 작은 경우에 이동시켜줍니다. 현재까지 등장한 숫자들로는 원하는 값을 만들 수 없었기 때문입니다. start pointer는 우리가 원하는 값을 찾았거나 그보다 값이 큰 경우에 이동시켜주는데 이는 현재까지 등장했던 숫자들을 이용하여 원하는 값을 찾은 이상 지금까지 포함된 숫자들에 새로운 숫자들을 더해서는 원하는 값을 찾을 수 없다는 가정이 포함되어있기 때문입니다.

아래의 예시를 통하여 실제로 어떻게 움직이는지 확인해보겠습니다. 아래와 같은 배열이 있을 때 합이 5가 되는 케이스가 몇 개 존재하는지 찾는다고 가정해보겠습니다. 우선 start pointer와 end pointer는 모두 0에 위치합니다. 현재 더해진 값이 없으므로 합도 0일 것입니다.

0	1	2	3	4	5	6	7	8	9	10
null(S, E)	1	2	3	4	2	5	3	1	1	2

이제 5를 만들기 위해서 end pointer를 이동시켜 보겠습니다. 그러면 E는 1을 합에 포함시킬 수 있습니다. 하지만 여전히 5는 되지 않았기 때문에 계속 합이 5보다 크거나 같은 값이 될 때까지 E를 이용시킵니다. 그러면 end pointer가 3이 되었을 때 최초로 합이 5를 넘게 됩니다. 아래와 같은 모습일 것입니다.

0	1	2	3	4	5	6	7	8	9	10
null(S)	1	2	3(E)	4	2	5	3	1	1	2

위와 같이 원하는 값을 넘어서는 경우에는 start pointer를 이동시킨다고 하였으므로 S를 5와 같거나 작아질 때까지 이동시켜줍니다. 이 경우에는 S가 index 2까지 이동하면 5가 됩니다. 그러므로 1차적으로 아래와 같은 모양이 됩니다.

0	1	2	3	4	5	6	7	8	9	10
null	1	2(S)	3(E)	4	2	5	3	1	1	2

이 때 처음 합이 5가 되므로 count를 하나 올려주고 그 다음 S를 오른쪽으로 이동시켜 줍니다. 그렇게 값이 커지거나 같으면 S를 이동시키고 값이 작아지면 E를 이동시키는 방식으로 반복적으로 pointer를 이동시켜주다보면 S와 E가 배열의 length에 다다를 때까지 배열에서 연속된 숫자의 합으로 5를 만들수 있는 모든 경우의 수를 구할 수 있습니다.

실제 문제는 백준의 수들의 합 2를 추천합니다. 아래는 문제 링크와 소스입니다.

2003번: 수들의 합 2

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

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine().trim());

        int N = Integer.parseInt(st.nextToken());

        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine().trim());

        int[] A = new int[N];

        for (int i = 0; i < N; i++) {

            A[i] = Integer.parseInt(st.nextToken());

        }

        int s = 0;

        int e = 0;

        int sum = 0;

        int rst = 0;

        while (true) {

            if (sum >= M)

                sum -= A[s++];

            else if(e > N - 1)

                break;

            else

                sum += A[e++];

            if(sum == M)

                rst++;

        }

        System.out.println(rst);

    }

}