[알고리즘] 10. 투 포인터, 슬라이딩 윈도우

zzoni·2021년 8월 13일

슬라이딩윈도우 알고리즘 투포인터

Algorithm

목록 보기

11/15

성향이 비슷한 둘...

🔵 투 포인터 (two pointers)

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

◾ 대표적인 유형 (2003 - 수들의 합)

백준 - 2003 수들의 합

문제 - N칸의 1차원 배열이 있다. 이 배열의 부분 배열 중 그 원소 합이 M이 되는 경우의 수를 구하여라.

문제 해결

구간합 배열로 구하면 시간복잡도는 O(N^2)이 나와 실패!

-> 포인터 2개를 준비한다. (s, e)
맨 처음에는 s = e = 0 이며, 항상 s <= e여야 한다.
이 포인터는 현재 부분배열의 시작과 끝을 가리키는 역할이다.
s가 가리키는 칸은 포함되고, e가 가리키는 칸은 포함되지 않도록 기준을 잡겠다.

s=e일 경우 그건 크기가 0인 아무것도 포함하지 않는 부분배열을 뜻한다.

이제! 밑의 과정을 해줍니다...

현재 부분합 = sum
while(N--){ // N번 반복!
    if(sum >= M || e==N) { // 만약 현재 부분합이 M이상이거나 이미 e==N이면 s++
          s++;
    }else e++; // 그렇지 않다면 e++
    if(sum==M) res++; // 현재 부분합 == M이면 결과++
}

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

🕐 시간복잡도

O(N)
매 루프마다 항상 투포인터 중 하나는 1씩 증가하고 있고, 각 포인터가 N번 누적 증가해야 알고리즘이 끝나기 때문에 O(N)

👉 예제 (N = 10, M = 5 인 경우)

예제 소스코드

#include <iostream>
#include <vector>

using namespace std;


int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int N, M;
    cin >> N >> M;

    vector<int> arr(N);

    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    int s = 0, e = 0, res = 0, sum = 0;

    while (true) {
        if (sum >= M) {
            sum -= arr[s++];
        }
        else if (e == N) break;
        else sum += arr[e++];

        if (sum == M) res++;

    }
    cout << res;

    return 0;
}

🔵 슬라이딩 윈도우 (sliding window)

투포인터와 비슷한 테크닉!

마치 창문을 한쪽을 밀면서 문제를 푸는 것과 모양새가 유사해서 붙여진 이름이다.
투 포인터처럼 구간을 훑으면서 지나간다는 공통점이 있으나, 슬라이딩 윈도우는 어느 순간에도 그 구간의 넓이가 동일하다는 차이점이 있다.

◾ 대표적인 유형 (2096 - 내려가기)

백준 - 2075 N번째 큰 수
배열을 다 저장해두지 않고 매번 크기가 N인 최소 힙에 넣고 빼는 것만 반복하는 풀이

백준 - 2096 내려가기 👉 얠 봐보자

문제 해결

O(3N)인 DP문제 같지만 메모리가 4MB로 제한되어있다...!

키 포인트는, 이전 정보는 필요하지만 모든 이전 정보가 필요하지는 않다는 것.

<라이님 설명 따옴>
/*
문제가 2개인데 최대 점수만을 들어 설명해 봅시다.

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

이때 S[i][0]은 max(S[i-1][0], S[i-1][1]),

S[i][1]은 max(S[i-1][0], S[i-1][1], S[i-1][2]),

S[i][2]는 max(S[i-1][1], S[i-1][2])겠죠.

여기서 DP를 사용해 자신보다 작은 문제, 즉 더 위의 행 문제 정보를 갖고 이번 행 문제를 풀기는 하는데

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

자신의 바로 위의 행 문제만 한 번이라도 정확히 해결해놧다면, 그 이후는 그 위를 두번 다시 참조할 필요가 없다는 말.
그래서 10만 행의 배열을 다 할당하지 않고, 바로 이전 행과 현재 행 이렇게 단 2개 행의 배열공간만 사용하여 문제를 해결할 수 있게 된다.

dp + 슬라이딩 윈도우

👉 예제 (백준 예제)

input

🕐 시간복잡도, ◎ 공간복잡도

O(N), O(1)

예제 소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <climits>

#include <vector>
#include <queue>

using namespace std;


int main() {
    std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    // pre : i-1행, temp : i행
    int premin[3]{ 0 }, premax[3]{ 0 }, tempmin[3]{ 0 }, tempmax[3]{ 0 };

    int N, j, temp; cin >> N;
    for (int i = 0; i < N; i++) {
        for (j = 0; j < 3; j++) {
            cin >> temp;
            tempmax[j] = temp + max(premax[1], (j == 1) ? max(premax[0], premax[2]) : premax[j]);
            tempmin[j] = temp + min(premin[1], (j == 1) ? min(premin[0], premin[2]) : premin[j]);
        }
        copy(tempmax, tempmax + 3, premax);
        copy(tempmin, tempmin + 3, premin);
    }

    sort(tempmax, tempmax + 3);
    sort(tempmin, tempmin + 3);
    cout << tempmax[2] << " " << tempmin[0];
    return 0;
}