[ 개념 ] 36. Two Pointer(투포인터), Sliding-Window(슬라이딩 윈도우)

Two Pointer & Sliding Window:facepunch:

> Two Pointer

---

1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태의 알고리즘!!

대표적인 유형으로는 백준 2003 : 수들의 합2

문제를 보겠습니다.

N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소 합이 M이 되는 경우의 수를 구하여라!?

모든 경우의 수를 다 테스트한다면, 구간 합을 구간합 배열로 O(1)만에 구한다고 해도 경우의 수가 이미 O(N²)이라 fail이다.

이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립하면 사용할 수 있는 알고리즘은 아래와 같다.

포인터 2개를 준비한다. (lo, hi), (l, r), (p, q), (s, e) 등등 명칭은 자유인데 여기서는 (s, e)로 하겠다.

맨 청므에는 s = e = 0이며 항상 s<=e 여야 한다.

이 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할이다.

저는 s가 가리키는 칸은 포함되고, e가 가리키는 칸은 포함되지 않도록 기준을 잡겠다.

s = e일 경우 그건 크기가 0인, 아무것도 포함하지 않는 부분 배열을 뜻한다. 이제 다음의 과정을 s<N동안 반복한다.

1. 만약 현재 부분합이 M이상이거나, 이미 e=N이면 s++
2. 그렇지 않다면 e++
3. 현재 부분합이 M과 같으면 결과++

말하자면 s,e를 무조건 증가시키는 방향으로만 변화시켜 가면서, 도중에 (s, e) 부분 배열의 합이 정확히 M이 되는 횟수를 세는 것이다.

두 번째 예제 (M=5)를 갖고 설명해 보겠다.

초기상태이다. 빨간색 포인터가 s, 파란색 포인터가 e이다.

e가 뒤로 움직일 때는 새로 포함한 원소를 S에 더하고, s가 뒤로 움직일 때는 새로 넘긴 원소를 S에서 빼는 식으로 현재 (s, e)의 합 S를 매번 쉽게 구할 수 있다.

처음엔 이렇게 e만 연속적으로 증가하게 된다. S가 계속 M보다 작기 때문이다. (마지막엔 S>=M)이 되었으므로...

이렇게 s를 한 칸 옮겼는데, 동시에 S=5인 경우를 만났다! 이 때 결과를 1증가시켜 준다.

대략 이런식으로 포인터들이 움직이게 된다.

여기서 2번째로 S=5인 지점을 만났다.

그 직후, s가 1증가하면서 s=e인 경우가 나온다.

계속 가다보면 세 번째로 S=5인 지점을 만나게 된다.

그 이후 조건에 맞춰 포인터를 증가시키다 보면 e가 배열 끝을 가리키게 되어 더 이상 증가할 수 없는 상태가 된다.

그렇게 되면 그냥 s만 증가시켜 가다가 s역시 배열 끝에 다다르면 종료해도 되고, 그냥 그 자리에서 루프를 끝내버려도 된다.

이렇게 해서 S=5인 경우는 3개 발견되었고, 그게 답이 맞긴 했지만

정말 이것만으로 존재하는 모든 답은 찾은걸까요?

현재 우리의 포인터가 [lo, hi]에 위치해 있고, 구간 합이 k인 구간 [L, H)가 하나 존재한다고 해보자. (합이 k인 구간을 세는게 목표)

이 때 우리가 앞으로 포인터를 이처럼 증가시키면 절대 [L, H)인 구간을 만나지 않고 지나칠 수 없음을 보이면 된다. 만약이라도 그렇게 지나치려면 방법은 두가지가 있다.

1. hi==H가 되기 전에 lo > L이 된다.
   • 하지만 이럴 수 없다. 포인터는 한칸씩 증가하니까 저렇게 지나가려면 최소한 lo = L인 시점이 한번은 존재한다.
   • 그런데 hi < H이고 lo = L 이라면 저 빨간 구간보다 현재 구간이 작고, 따라서 구간합이 k보다 작다.
   • 따라서 이 상황에서는 무조건 hi를 증가시킬 수 밖에 없고, hi가 H까지 다다르기 전에는 증가를 멈추지도 못한다.
2. lo = L이 되기 전에 hi > H가 된다.
   • 역시 이것도 안된다. 위와 아주 똑같이 논파할 수 있다.
   • hi가 H를 지나쳐 가려면 hi = H인 시점이 한번은 존재하는데, 이 때 lo < L이라면 해당 구간의 합이 k보다 반드시 크기 때문에 여기서 hi를 증가시킬 수가 없다!

이것들은 모두 원소가 다 자연수이기 때문에 성립한다.

#include <cstido>
using namespace std;

int main(){
    int N, M, arr[10000];
    scanf("%d %d", &N, &M);
    for(int i=0; i<N; i++)
        scanf("%d", arr+i);

    int result = 0, sum = 0, lo = 0, hi = 0;
    while(1){
        if(sum >= M) sum -= arr[lo++];
        else if(hi == N) break;
        else sum += arr[hi++];
        if(sum == M) result++; 
    }
    printf("%d\n", result);
}

놀랍게도 이 알고리즘의 시간복잡도는 O(N)이다.

이 알고리즘은 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝난다.

이와 비슷하게 슬라이딩 윈도우(sliding window)라는 유형의 테크닉이 존재한다.

이건 마치 창문을 한쪽으로 밀면서 문제를 푸는 것과 모양새가 유사해서 붙여진 이름..

투포인터처럼 구간을 훑으면서 지나간다는 공통점이 있으나 슬라이딩 윈도우는 어느 순간에도 그 구간의 넓이가 동일하다는 차이점이 있다 !!

> Sliding Window

---

대표문제로는 백준 2075 : N번째 큰수

이 문제는 배열을 다 저장해두지 않고, 매번 크기가 N인 최소 힙에 넣고 빼는 것만 반복하는 풀이가 존재한다.

이걸 크기가 N인 창문을 N² 공간에서 미는 슬라이딩 윈도우라고 할 수 도 있다.

하지만 진짜로 슬라이딩 윈도우를 소개하는 목적은...!!!??

백준 2096 : 내려가기

척보면 상당히 쉬운 DP이다.하지만 메모리 제한이 4MB????

키포인트는 바로 이전 정보를 필요로 하지만 모든 이전 정보가 필요하지는 않다는 것!!

S[i][j]를 i행 j열까지 내려오면서 얻을 수 있는 최대 점수라 하죠. i는 충분히 크고요.

바로 자기 바로 위의 행에 관한 정보만 쓰고, 그 위는 쳐다보지도 않는다.

자신의 바로 위의 행 문제만 한번이라도 정확히 해결해 놨다면, 그 이후는 그 위를 두번 다시 참조할 필요가 없다는 말이다!!

그래서 10만 행의 배열을 다 할당하지 않고, 바로 이전 행과 현재 행 이렇게 단 2개의 행의 배열 공간만 사용하여 문제를 해결할 수 있다.

// 백준 2096 : 내려가기
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
    int colMax[3] = {0}, colMin[3] = {0}, tempMax[3] = {0}, tempMin[3] = {0};
    int N;
    scanf("%d", &N);
    for(int i=0; i<N; i++){
        for(int j=0; j<3; j++){
            scanf("%d", tempMax+j);
            tempMin[j] = tempMax[j];
            tempMax[j] += max( colMax[1], (j==1)?max(colMax[0], colMax[2]):colMax[j] );
            tempMin[j] += min( colMin[1], (j==1)?min(colMin[0], colMin[2]):colMin[j] );
        }
        // colMax, colMin 배열을 temp 배열로 덮어쓰기하여 다음 루프에서 사용
        memcpy(colMax, tempMax, sizeof(int)*3);
        memcpy(colMin, tempMin, sizeof(int)*3);
    }
    sort(colMax, colMax+3);
    sort(colMin, colMin+3);
    printf("%d %d\n", colMax[2], colMin[0]);
}

이코드가 슬라이딩 윈도우 + DP로 문제룰 푸는 코드이다.

colMax와 colMin이 이전 행, 즉 i-1행의문제들의 결과를 갖고 있는 배열이고 이걸 사용해 tempMax, tempMin 배열에 현재 행, 즉 i행의 문제들을 풀어서 저장한다.

그리고 루프가 끝날 때마다 temp 배열들을 colMax, colMin 배열로 덮어쓰기하여 다음 루프에 사용할 수 있도록 합시다. 이 시점에서 i-1행의 문제 답들은 버려지는 거죠.

이렇게 해서 맨 마지막에 colMax, colMin 배열에 남겨진 건 제일 마지막 행에 관한 문제들 뿐이겠네요.

이렇게 하여 시간복잡도는 여전히 O(N)이지만 공간복잡도가 그냥 O(1)이 되어버렸습니다.

이 슬라이딩 윈도우 + DP의 조합은 정말 보기 쉽지 않지만, 마음먹고 적용하려면 사실 적용할 수 있는 범위는 넓습니다.

그리고 최단경로를 구하는 유명한 알고리즘 중 하나인 플로이드 알고리즘이 의외로 이 슬라이딩 윈도우 기법을 사용합니다.

관련 추천 문제

2003번: 수들의 합 2

위에서 설명한 문제입니다.

1644번: 소수의 연속합

N까지 존재하는 소수를 에라토스테네스의 체로 뽑고 그대로 투 포인터 알고리즘을 적용하면 끝입니다.

1806번: 부분합

부분합이 정확히 S가 아니라 S 이상이라지만,

우리의 투 포인터 알고리즘 자체가 현재 부분합이 S 이상이면 가능한 한 구간 크기를 작게 만드려고 애쓰기 때문에 이 문제가 투 포인터로 풀립니다.

2230번: 수 고르기

부분합이 아니라 차이에 관한 문제지만 투 포인터로 비슷하게 풀 수 있습니다.

차이가 M 이하면서 hi가 끝에 도달하지 않았으면 hi를, 아니면 lo를 증가시킵니다.

1484번: 다이어트

현재 몸무게를 B, 원래 몸무게를 A라 하면 B^2 - A^2 = G인 경우를 다 찾는 겁니다. 이때 A, B는 다 자연수여야 한다는군요.

s = e = 1로 잡고, e^2 - s^2가 G 이상이면 s를 증가시키고 아니면 e를 감소시키는 식으로 하면서 투 포인터 알고리즘을 진행하면 됩니다.

G가 최대 10만이고, 저 식을 만족하는 A, B 수가 그리 많지 않기에 알고리즘이 아주 긴 시간 동안 안 끝나지는 않습니다.

알고리즘을 언제 끝내느냐? s와 e가 불과 1 차이밖에 안 나는데 e^2 - s^2가 G보다 크면 종료하면 됩니다. 이때부터는 인접한 수들마저도 항상 제곱수의 차가 G보다 커서 절대 더 이상 답이 나올 수가 없습니다.

2038번: 골롱 수열 (★)

문제 설명이 상당히 어려운데, f(k)들로 이루어진 것 자체가 수열입니다.

즉 골롱 수열의 1번째 항이 f(1), 2번째 항이 f(2), ... 이렇습니다.

즉, 골롱 수열 전체에서 k가 f(k)번 등장한다는 소리입니다. f(k)는 자연수고요.

먼저 f(1) = 1일 수밖에 없습니다. f(1) > 1이라면 일단 첫 번째 항이 1이 아니죠.

그러나 f(1) > 1이니까 1이 반드시 이 수열에 등장은 한다는 건데, 등장하게 되면 첫 번째 항보다 작아서 단조증가 수열이라는 법칙이 깨지게 됩니다.

따라서 맨 앞에 1이 하나 있고, 그 바로 뒤에는 2가 오게 되어서 f(2) = 2가 되어 2 역시 수열에 2번 등장하게 됩니다. 이런 식으로 수를 끼워맞추다 보면...

1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 ...

이런 형태의 수열을 얻을 수 있게 됩니다.

이제 여기서 n이 주어지면 f(n)을 구하라는 건데, 이때는 1씩 증가하며 k를 가리키는 포인터 p,

그에 맞춰 여러 칸씩 증가하며 k가 골롱 수열에서 처음 등장하는 위치로 옮겨가는 포인터 q

이렇게 2개를 두고 조작해가며 q가 n 이상이 될 때까지 p, q를 증가시켜 가면 됩니다.

n이 최대 20억이라서 시간이나 메모리가 부족할 수도 있으나, 실험 결과 n = 20억일 때 f(n)은 몇백만 근처까지만 다다른다고 합니다. 따라서 수열값을 저장해가며 풀 수 있습니다.

2531번: 회전 초밥

원형으로 된 곳에서 돌리는 슬라이딩 윈도우 문제입니다. 원형인 것에 주의해서, 최대 3000가지의 초밥 종류마다 현재 구간에 몇 개 속해 있는지 세는 배열을 잘 처리하면서 쭉 돌려주면 됩니다.

2096번: 내려가기

위에서 설명한 문제입니다.

2293번: 동전 1 (★)

동전 2보다 충분히 어려운데 어째 푼 사람 수는 더 많은 이상한 문제...

역시 슬라이딩 윈도우를 접목한 바텀업 방식으로 DP를 풀어야 합니다.

coin(n, k)가 1~n번째 동전만 사용하여 k원을 나타내는 방법의 가짓수라고 한다면 이 문제를 푸는 데 당장은 coin(n-1, k) 형태의 바로 아랫 단계 문제들의 답만 필요할 것입니다.

따라서 k의 최댓값이 10000이므로 10001칸짜리 배열 2개를 만들어서 덮어써가며 풀면 됩니다.