투포인터 알고리즘, 슬라이딩 윈도우 알고리즘, 구간합 알고리즘

투 포인터와 슬라이딩 윈도우 알고리즘은 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N^2) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다는 공통점이 있다.

그렇다면 이 두 알고리즘의 차이점은 무엇까?

바로, 부분 배열 길이의 변화 여부이다.
더 쉽게 말해서, 투 포인터 알고리즘은 부분 배열의 길이가 가변적이지만 슬리이딩 윈도우 알고리즘은 부분 배열의 길이가 고정적이다.

---

투 포인터 알고리즘

어떤 특정 조건을 만족하는 연속되고 가변적인 구간을 구할 때 O(N) 으로 풀 수 있도록 도와주는 알고리즘.

 

2개의 포인터를 사용하여 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간을 찾는다.

모든 연속 구간을 잡는다면 O(N^2)이 될 것이지만 투 포인터 알고리즘을 사용하면 O(N)의 시간복잡도로 풀 수있다.

두 포인터가 각각 N 번 움직이기 때문에 N+N=2N번의 연산이 있는 셈이다.

즉, O(2N) = O(N)이 된다. 

어떤 구간을 찾는 문제일 때 입력 크기가 아주 크다면 투 포인터 알고리즘을 고려하여 풀자.

 

2 개의 포인터 中
right 포인터는 어떤 조건일 때 증감시키고, left 포인터는 어떤 조건일 때 증감시킬지 결정해야 한다.

 

• 투포인터 알고리즘 문제의 유형
  
  1. 포인터 2개가 같은 방향으로 진행하는것
  2. 포인터 2개가 양끝에서 시작하여 반대로 진행하는 것
  3. 포인터 하나는 한쪽 방향으로만 진행하고, 다른 포인터는 양쪽으로 이동하는 것

 

간단하게 포인터 2개가 같은 방향으로 진행하는 문제를 풀어보자.

문제는 아래와 같이 자연수로 구성된 수열에서 합이 5인 부분의 연속 수열의 개수를 구하는 것이다.

 

 

이중 반복문을 이용한 완전 탐색으로 문제를 해결할 수도 있지만 그럴 경우 O(N^2)의 시간 복잡도가 발생하게 되며,

그보다 적은 시간복잡도를 통해 문제를 해결해야 하는 경우라면 투 포인터 알고리즘을 활용하여 O(N)의 시간복잡도로 문제를 해결할 수 있다.

 

int solution(int n, const vector<int>& arr) 
{
    int result = 0; // 부분 수열의 요소의 전체 합이 n인 부분 수열의 개수
    int sum = 0;    // 부분 수열의 요소 전체 합
    int end = 0;    // 투 포인터에서 끝 점에 해당된다.

    // 시작점 start를 배열 시작부터 오른쪽으로 한 칸씩 옮긴다.
    for (int start = 0; start < arr.size(); start++)
    {
        // 끝점 end를 가능한 만큼 이동
        while (sum < n && end < arr.size())
        {
            sum += arr[end];
            end++;
        }

        if (sum == n)
            result++;

        sum -= arr[start];  // 시작점을 옮기기 전에 합에서 뺀다.
    }

    return result;
}

 

---

슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 알고리즘은 연속되는 투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만

부분 배열의 크기가 고정적이다.

또 다른 차이점은 투 포인터 알고리즘은 부분 배열의 길이가 가변적이기 때문에 부분 배열의 구간을 정할 2개의 포인터 변수가 필요한 반면, 슬라이딩 윈도우 알고리즘은 부분 배열의 길이를 고정적으로 잡기 때문에 포인터 변수가 2개일 필요가 없다.

 

구간의 고정 길이를(즉 창문의 너비를) L 이라고 할 떄, 창문을 한 칸 옮기더라도 옮기기 전 창문안에 있던 L - 1 칸은 겹치게 된다.

• 기존 모습 : 🟨🟪🟪🟪🟪🟨🟨
• 다음 모습 : 🟨🟨🟪🟪🟪🟪🟨

 

기존 구간과 새 구간의 🟨🟪🟥🟥🟥🟪🟨 빨간 부분은 겹치게 된다. 이미 🟥🟥🟥은 새 구간에도 포함이 되어 있으므로 새 구간에서는 빠지게 된 앞의 🟪 와 새 구간에 포함되게 된 🟪 만 비교하게 되면 더 효율적일 것이다. 

이렇게 O(N^2)를 피할 수 있다. 이전의 결과를 써먹는 방향으로 접근하자.

슬라이딩 윈도우 문제 유형

• 구간합
  
  • 기존의 구간의 합이 S 이고 새로운 구간에선 빠지는 맨 앞 원소가 A 고 새로운 구간에 들어오게 된 원소를 B 라고 하면 새로운 구간의 합은 S - A + B 가 된다. 즉, 이 합의 과정이 O(1) 밖에 안되는 것이다. 일일이 새로운 구간의 합을 또 구할 필요가 없다. 따라서 전체적인 과정은 O(N) 이 된다. (맨 처음 창문의 합을 구할 때만 O(W))
• Anagram 찾기

 

문제

현수의 아빠는 제과점을 운영합니다.

 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속 된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다.
만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 

이때 K=3이면
12 15 11 20 25 10 20 19 13 15
연속된 3일간의 최대 매출액은 11+20+25=56만원입니다. 여러분이 현수를 도와주세요.

 

[입력설명]
첫 줄에 N(5<=N<=100,000)과 M(2<=K<=N)가 주어집니다.
두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 500이하의 음이 아닌 정수입니다.
[출력설명]
첫 줄에 최대 매출액을 출력합니다.

입력 예제
10 3
12 15 11 20 25 10 20 19 13 15

출력 예제
56

출처 : https://velog.io/@codenmh0822/%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

int solution(int n, int k, const vector<int>& arr)
{
    int result = 0; // 길이 k의 부분 수열의 요소 전체 합의 최댓값
    int sum = 0;    // 특정 부분 수열의 전체 합

    // 처음 k개의 요소 합을 계산
    for (int i = 0; i < k; i++)
    {
        sum += arr[i];
    }

    result = sum; // 처음 k개의 합을 최댓값으로 설정

    // 슬라이딩 윈도우 방식으로 최대 합을 구함
    for (int i = k; i < n; i++) 
    {
        sum += (arr[i] - arr[i - k]); // 현재 윈도우에서 k번째 요소 더하고, 이전 요소는 뺌
        result = max(result, sum);    // 현재 최대값과 비교하여 더 큰 값 선택
    }

    return result;
}

int main()
{
    int n = 10;
    int k = 3;
    vector<int> arr = { 12, 15, 11, 20, 25, 10, 20, 19, 13, 15 };

    cout << solution(n, k, arr) << endl;  // 출력: 56
    return 0;
}

 

---

구간 합(Prefix Sum)

위의 두 알고리즘과 비슷하게 배열의 특정 연속된 구간에 대한 처리를 목적으로 하는 알고리즘이다.

차이를 비교해보자면 위의 두 알고리즘은 0~특정길이의 구간에 대한 처리를 한다면 구간 합은 특정위치 a,b가 주어졌을 때 배열에서 a~b의 구간에 대한 처리를 다룬다고 할 수 있다.

 

 

구현

배열의 앞에서부터 특정 위치까지의 합인 접두사 합을 활용하는 방식을 사용

 

 

int solution(int l, int r, const vector<int>& arr)
{
    int sum = 0;
    vector<int> prefixSum(1, 0); // prefixSum[0] = 0으로 초기화

    // prefix sum 배열 생성
    for (int i = 0; i < arr.size(); i++)
    {
        sum += arr[i];
        prefixSum.push_back(sum);
    }

    // 특정 구간의 합 계산 (1-based index를 고려하여 l-1 사용)
    return prefixSum[r] - prefixSum[l - 1];
}

int main() 
{
    vector<int> arr = { 10, 20, 30, 40, 50 };
    cout << solution(2, 5, arr) << endl; // 2~5 구간의 합 (출력: 140)
    return 0;
}