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

이번 게시글에서 정리할 기법은 투포인터와 슬라이딩 윈도우 입니다.

두 기법은 유사해서 하나로 묶었는데, 우선 투 포인터를 살펴보겠습니다.

 

투포인터는 1차원 배열에서 배열 원소를 가리키는 두 개의 포인터를 조절해가면서 원하는 답을 찾는 기법입니다.

문제를 보면서 살펴보겠습니다.

 

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

2003번 문제는 N개의 수로 이루어진 배열이 있을 때, 연속된 부분 수열의 합이 M을 만족하는 경우의 수를 구하는 문제입니다. 입력을 받으면서 구간합을 미리 구해놓는다고 해도, 모든 경우의 수를 살펴본다고 하면 O(\(N^2\))이기 때문에 시간초과가 발생할 것 같지만, 일단 발생하지는 않더라구요(이중 반복문으로 모든 경우의 수를 살펴보면서, 부분합이 M보다 커지면, 내부 반복문을 빠져나오는 것으로 해결됩니다). 오늘 목적은 투포인터를 알고자하는 것이니 투포인터로 문제를 한 번 해결해보겠습니다.

 

투포인터는 다음과 같은 과정을 통해서 진행됩니다.

1. 부분 배열의 시작과 끝의 값을 가리키는 포인터(lo, hi)를 두 개를 지정합니다. 각 포인터는 배열의 index 값이 되고, 두 포인터 사이의 부분 배열은 lo 포인터는 포함하고, hi는 포함하지 않는 [lo, hi)의 범위입니다. lo와 hi의 초기값은 모두 0입니다.

2. 현재 포인터가 가리키는 범위의 부분합을 확인합니다. 부분합의 초기값은 0입니다.

2-1. 현재 부분합이 M보다 크거나 같다면, lo가 가리키는 값을 부분합에서 빼주고 lo++

2-2. hi의 값이 N이라면 반복문 종료

2-3. 현재 부분합이 M보다 작다면, hi가 가리키는 값을 부분합에 더해주고 hi++

3. 현재 부분합이 M과 같다면, 결과값 +1

반복문을 빠져나올 때 까지 2 ~ 3 과정을 반복하게 됩니다. 

 

이해가 가지 않는다면, 두번째 예제 입력을 가지고 한 번 직접 포인터를 가리키면서 확인해보면 이해가 빠를 것 같습니다. 

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, A[10000];
int main() 
{
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]);

	int lo = 0, hi = 0, sum = 0, result = 0;

	while (1)
	{
		if (sum >= M)
			sum -= A[lo++];
		else if (hi == N)
			break;
		else
			sum += A[hi++];

		if (sum == M)
			result++;
	}

	printf("%d\n", result);

	return 0;
}

코드는 다음과 같습니다. 

위 알고리즘의 시간복잡도는 O(N)이 되는데, 매 루프마다 포인터가 1씩 증가하게 되는데, 최악의 경우로 두 포인터 모두 N에 도달해야 끝이 나는 경우라 하더라도 O(N + N) = O(N)이 됩니다.

 

유사한 문제로는 

1806 부분합

1644 소수의 연속합

2470 두 용액

2473 세 용액

2230 수 고르기

등이 있습니다. 

www.acmicpc.net/problem/tag/80

두 포인터 - 1 페이지

위 경로에 두 포인터 태그로 묶인 문제들이 있으니 골라서 풀어보는 것도 좋습니다.

 

 

다음은 슬라이딩 기법입니다. 

투포인터와 유사하게 구간을 살펴보면서 이동해가는데, 그 구간의 길이가 일정하다는 차이점이 있습니다.

www.acmicpc.net/problem/2096

2096번: 내려가기

위 문제를 한 번 살펴봅시다. 

맨 처음 세 개의 숫자 중에서 하나를 골라서 시작해서 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있는 조건이 있습니다. 그렇게 따라 내려가서 마지막에 얻을 수 있는 최소 점수와 최대 점수를 구하는 문제입니다. 

 

위 문제는 한 줄에 3개의 숫자가 있고, 현재 줄에서 구한 값들로 다음 줄의 결과를 구하면서 내려가면 됩니다. 즉, 3개의 값들로 이루어진 구간을 가지고 밑으로 내려가면서 3개씩 체크를 하는 것이죠. 동적계획법으로도 풀리지만, 이 문제의 메모리제한이 4MB이기 때문에 모든 값들을 저장해서는 풀 수 없고, 슬라이딩 기법을 사용해야합니다.

 

최대점수와 최소점수를 구해야하는데, 각각 나누어서 살펴보겠습니다.

여기서 MaxScore[i]은 현재 줄에서의 i열 위치의 최대점수이고, MinScore[i]는 현재 줄에서 i열 위치의 최소점수입니다.

매 층마다 input[i]에 각 열의 입력을 받고, tmp[i]에 이전 줄에서 i열의 최대점수를 저장합니다. 첫 번째 줄이었다면, 이전 층의 최대점수는 모두 0이 됩니다.

그리고 MaxScore 값을 업데이트해주는데, 다음과 같습니다.

MaxScore[0] = max(tmp[0] + input[0], tmp[1] + input[0])

MaxScore[1] = max(max(tmp[0] + input[1], tmp[1] + input[1]), tmp[2] + input[1])
MaxScore[2] = max(tmp[1] + input[2], tmp[2] + input[2])

최소점수도 동일하게 tmp[i]에 MinScore[i]를 저장하고 다음과 같이 MinScore를 업데이트 해줍니다.

MinScore[0] = min(tmp[0] + input[0], tmp[1] + input[0])
MinScore[1] = min(min(tmp[0] + input[1], tmp[1] + input[1]), tmp[2] + input[1])
MinScore[2] = min(tmp[1] + input[2], tmp[2] + input[2])

 

이처럼 동적계획법을 사용하지만, 위쪽 행의 입력값은 더 이성 저장할 필요가 없이 기존의 입력들로 각 열의 최대점수와 최소점수를 구해 놨다면, 현재 입력만을 가지고 최대, 최소 점수를 갱신할 수 있습니다.

그래서 여기서는 int형 배열 4개를 가지고, 문제를 해결할 수 있습니다. 공간복잡도를 O(1)로 대폭 낮추어서 문제를 해결할 수 있습니다. 

 

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int N, MaxScore[3] = { 0, 0, 0 }, MinScore[3] = { 0, 0, 0 };
    scanf("%d", &N);

    for (int i = 0; i < N; i++)
    {
        int input[3], tmp[3];
        scanf("%d %d %d", &input[0], &input[1], &input[2]);

        tmp[0] = MaxScore[0], tmp[1] = MaxScore[1], tmp[2] = MaxScore[2];
        MaxScore[0] = max(tmp[0] + input[0], tmp[1] + input[0]);
        MaxScore[1] = max(max(tmp[0] + input[1], tmp[1] + input[1]), tmp[2] + input[1]);
        MaxScore[2] = max(tmp[1] + input[2], tmp[2] + input[2]);

        tmp[0] = MinScore[0], tmp[1] = MinScore[1], tmp[2] = MinScore[2];
        MinScore[0] = min(tmp[0] + input[0], tmp[1] + input[0]);
        MinScore[1] = min(min(tmp[0] + input[1], tmp[1] + input[1]), tmp[2] + input[1]);
        MinScore[2] = min(tmp[1] + input[2], tmp[2] + input[2]);
    }

    int MinResult, MaxResult;

    MinResult = min(min(MinScore[0], MinScore[1]), MinScore[2]);
    MaxResult = max(max(MaxScore[0], MaxScore[1]), MaxScore[2]);

    printf("%d %d", MaxResult, MinResult);

    return 0;
}

 

12891 DNA 비밀번호

12891번: DNA 비밀번호

슬라이딩 기법으로 풀어본만한 문제입니다. 주어진 부문문자열 길이를 구간으로 훑어가면서 만족하는지 체크하면 됩니다.

 

www.acmicpc.net/problem/tag/68

슬라이딩 윈도우 - 1 페이지

위 알고리즘 분류에서 슬라이딩 윈도우 기법으로 풀 수 있는 문제들이 있으니, 참조바랍니다. 사실.. 많이 풀어보지는 않았지만, 대다수가 슬라이딩기법만으로는 풀기 어려운 문제들이 꽤 있는 것 같긴 합니다.