[알고리즘] 투포인터

문제상황

---

• 배열A에서 A[i] ~ A[j] 까지의 합을 구하려면?
  - 그냥 더하면 O(n)이므로, 연산횟수가 엄청남.

해결 방법

---

1. 누적합
   • 배열B를 만들어서, B[i]에 0~i까지의 합을 저장해놓기
   • i부터 j까지를 구하고 싶다고 하면, B[j]-B[i-1]하면됨.
2. 슬라이딩 윈도우
   • 특정 조건을 만족하는(구간의 길이) 연속 구간을 구할 때 O(n)으로 풀 수 있도록 도와주는 알고리즘
   • 구간의 길이가 고정적이기 때문에 포인터가 2개일 필요가 없음. 하나만 있으면 길이를 아니까 끝이 어딘지 알 수 있기 때문
   • 구간합
     기존 구간의 합이 S일때, 새로운 구간은 맨앞 원소 A가 빠지고 새로운 원소 B가 들어오는 S-A+B형태
     (합연산이 O(1)임)
3. 투포인터
   • 2개의 포인터로 배열을 탐색하여 답을 찾음
   • while문으로 주로 구현
   • O(n²)문제를 O(n)으로 풀기 가능

투포인터 방법

---

1. 2개의 포인터가 다른 위치에서 시작해서 서로에게 다가가기
   • 배열이 정렬되었을 때에만 성립하는 경우가 많음
2. 2개의 포인터가 같은 위치에서 시작해서 같은 방향으로 이동탐색
   • 슬라이딩 윈도우는 포인터 사이의 거리를 고정한 2번방식 투포인터임

• 2개의 포인터를 사용하여 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간을 찾는것
• 어떤 구간을 찾는 문제 / 입력 크기가 아주 큼 = 투포인터 알고리즘 고려하기!
  

문제풀이

---

포인터 2개가 같은 방향으로 진행

//BOJ 2003
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> a;

int twoPointer(int size, int num) {
    int count = 0;
    int sum = a[0];
    int start = 0; int end = 0; //얘네가 포인터 역할함
    while(end < size) {
        if(sum < num) {
            end++;
            if(end < size) sum+= a[end];
        }
        else if (sum > num) {
            sum -= a[start];
            start++;
        }
        else {
            sum -= a[start];
            start++;
            end++;
            if(end < size) sum += a[end];
            count++;
        }
    }
    return count;
}

int main() {
    int n, m;
    cin >> n >> m;
    a.assign(n, 0);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << twoPointer(n, m);
}