투 포인터(Two pointer)와 슬라이딩 윈도우(Sliding Window)

🔹 투 포인터 (Two pointer)

• 1차원 배열에서 각각 다른 원소를 가리키는 2개의 포인터를 조작해 가며 원하는 값을 찾을 때까지 탐색하는 알고리즘이다.
• 이러한 특성 때문에, 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 문제에 적용 가능하다.
• 투 포인터 알고리즘은 2가지 유형이 존재한다.
  • 2개의 포인터 변수 시작점이 배열의 시작점인 경우
  • 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우

 

위에 적힌 투 포인터 알고리즘의 2가지 유형을 각각 문제를 통해 알아보자.

 

🔸 2개의 포인터 변수 시작점이 배열의 시작점인 경우

예를 들어, 백준 2003 수들의 합 2 문제에서는 N개의 수열에서 특정 구간(i부터 j)의 합이 M이 되는 경우의 수를 알고 싶다.

 

먼저, 두 포인터 start와 end는 시작점 0에서 같이 탐색을 시작한다.

 

end 포인터를 한 칸씩 움직여 start와 end 사이에 있는 원소들의 구간합(sum)을 구해준다.

 

 

sum의 값이 M보다 큰 경우, sum에서 현재 start 위치 값을 빼주고 start 포인터를 한 칸 앞으로 이동한다.

sum과 M이 같은 값일 땐 cnt를 증가시켜 준다.

 

end 포인터가 N에 도달하면 while문을 빠져나온다.

💭 Java  Code

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2};
        int n = 10, m = 5;

        int start = 0, end = 0;
        int sum = 0, cnt = 0;
        while (true) {
            if (sum >= m) {
                sum -= arr[start++];
            } else if (end == n) break;
            else {
                sum += arr[end++];
            }

            if (sum == m) cnt++;
        }

        System.out.println(cnt);
    }
}

 

🔸 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우

예를 들어, 백준 2470 두 용액 문제에서는 양의 정수로 나타내진 산성 용액과 음의 정수로 나타내진 알칼리성 용액을 혼합하여 특성 값이 0에 가장 가까운 용액을 만들어내는 두 용액을 알고 싶다.

 

주어진 배열에서 0에 가장 가까운 용액을 만들어야 하기 때문에, 먼저 배열을 정렬해 준다.

 

양쪽 끝에 start 포인터와 end 포인터를 두고 서로 중앙을 향해 거리를 좁혀지는 형태로 탐색하며 용액을 골라주면 된다.

arr[start] + arr[end] = -92 < 0 이므로 값이 더 커져야 한다.

 

배열은 오름차순으로 정렬되어 있으므로 두 수의 합이 커지기 위해서는 start 포인터를 한 칸 이동해줘야 한다.

arr[start] + arr[end] = 5 > 0 이므로 값이 더 작아져야 한다.

 

두 수의 합이 작아지기 위해서는 end 포인터를 한 칸 이동해줘야 한다.

 

위와 같은 방식으로 탐색을 진행하다 start < end가 되는 시점에서 탐색을 종료해 주면 된다.

💭 Java  Code

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {-99, 4, 7, -1, -2};
        int n = 5;
        Arrays.sort(arr);

        int start = 0, end = n-1;
        int min = Integer.MAX_VALUE;
        int[] ans = new int[2];
        while (start < end) {
            int sum = arr[start] + arr[end];

            if (min > Math.abs(sum)) {
                min = Math.abs(sum);
                ans[0] = arr[start];
                ans[1] = arr[end];

                if (sum == 0) break;
            }

            if (sum < 0) start++;
            else end--;
        }

        System.out.println(ans[0] + " " + ans[1]);
        // 출력 : -2 4
    }
}

 

🔹 슬라이딩 윈도우 (Sliding Window)

• 투 포인터와 유사하지만, 부분 배열의 길이를 고정해서 탐색하는 방식의 알고리즘이다.
• 투 포인터 알고리즘은 구간의 길이를 가변적으로 잡기 때문에 구간의 양쪽 끝이 되는 포인터 2개가 필요하다.
• 반면, 슬라이딩 윈도우 알고리즘은 구간의 길이를 고정적으로 잡기 때문에 포인터가 하나만 있어도 배열의 끝이 어딘지 알 수 있다.

 

이제 슬라이딩 윈도우 알고리즘을 문제를 통해 알아보자.

 

예를 들어, 백준 2559 수열 문제에서는 수열에서 연속적인 k일의 온도의 합이 최대가 되는 값을 알고 싶다.

 

k 크기의 윈도우를 배열의 처음부터 끝까지 탐색하여 윈도우 내의 수의 합을 구한다고 생각해 보자.

먼저 0번 인덱스부터 k-1번째 인덱스까지 더해 sum을 구해준 후 최댓값으로 설정해 준다.

 

윈도우를 오른쪽으로 한 칸 움직이면,

새로 윈도우에 포함된 오른쪽 값을 더하고 윈도우에서 빠지게 된 왼쪽 값을 빼주면 그다음 위치의 합을 구할 수 있다.

 

두 개의 합을 비교하여 최댓값을 갱신해 주고, 이와 같은 방식으로 배열 끝까지 반복하여 탐색한다.

💭 Java  Code

public class Main {
    public static void main(String[] args) {
        int n = 10;
        int k = 2;

        int[] arr = {3, -2, -4, -9, 0, 3, 7, 13, 8, -3};

        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }

        int ans = sum;
        for (int i = k; i < n; i++) {
            sum += (arr[i] - arr[i-k]);
            ans = Math.max(ans, sum);
        }

        System.out.println(ans);
    }
}

 

 

 

 

 

 

 

 

📃 reference

• https://kkmdailylog.tistory.com
• https://loosie.tistory.com/319
• https://velog.io/@codenmh0822