이 글의 내용은 다음과 같습니다:

1. 투포인터
   1.1 백준 1253 좋다

2. 슬라이딩 윈도우
   2.1 백준 12891번: DNA 비밀번호

---

이 두 가지 알고리즘의 공통점은 1차원 배열 반복 탐색할 때 시간 복잡 O(N^2) 에서 O(N) 으로 줄일 수 있습니다.

다른 점은 투 포인터의 경우 두 인덱스 start, end를 조건에 따라 독립적으로 이동시키며 구간을 늘리거나 줄여서 배열을 탐색합니다.

반면 슬라이딩 윈도우는 고정 크기의 윈도우를 유지한 채 한 칸씩 이동하면서 들어오는 원소 && 빠지는 원소만 O(1)로 반영해 문제를 해결합니다.

---

1. 투 포인터

• 투 포인터는 두 개의 포인터 start(left), end(right) 이용해 값을 탐색하는 알고리즘입니다.
  

1.1) 1253 좋다

• sort() 함수를 이용해 배열 정렬해 줍니다
• 배열 양 끝에서 i(start)=0 와 j(end)=N-1 포인터를 지정해 두 수의 합이 find과 같으면 res 증가 시켰습니다

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

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

    int N;
    cin >> N;
    vector<int> A(N,0);

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

    sort(A.begin(), A.end());
    int res = 0;

    for(int k=0; k<N; k++) {
        long find = A[k];
        int i = 0, j = N-1;

        while(i < j) {
            if(A[i] + A[j] == find) {
                if(i != k && j != k) { //서로 다른 수의 합인지 체크
                    res++;
                    break;
                }
                else if (i==k) i++;
                else if (j==k) j--;
            }
            else if(A[i] + A[j] < find) i++;
            else j--;
        }
    }

    cout << res;
}

---

2. 슬라이딩 윈도우

슬라이딩 윈도우는 투 포인터와 유사한데 윈도우의 크기는 고정됩니다.

2.1) 12891번: DNA 비밀번호

• 문제 요약: 문자열이 {A, C, G, T} 로만 이루어진 DNA 문자열에서 길이 S의 모든 부분문자열을 검사해 각 문자 A, C, G, T가 최소 몇 번 이상 등장해야 한다는 조건을 모두 만족하면 비밀번호로 인정하여 개수를 센다

• 풀이 과정:

  • Step 1: 체크 배열(checkArr) 저장
  • Step 2: 윈도우에 포함된 문자로 현재 상태 배열 (myArray) 만든다. myArr && checkArr 비교
  • Step 3: 3: 윈도우를 한 칸씩 이동해 myArr 업데이트한다. 계속해서 myArr && checkArr 비교한다

#include<iostream>
using namespace std;

int checkArr[4];
// myArr[i]: 슬라이딩 윈도우 안에서 각 문자가 나온 현재 개수
int myArr[4];
// check: 4가지 조건(A/C/G/T) 중에서 요구에 도달한 항목 수
int check = 0;
void Add(char c);
void Remove(char c);

void Add(char c) { //새로 들어온 문자를 처리하는 함수
    switch (c) {
        case 'A':
            myArr[0]++;
            if (myArr[0] == checkArr[0]) check++;
            break;
        case 'C':
            myArr[1]++;
            if (myArr[1] == checkArr[1])  check++;
            break;
        case 'G':
            myArr[2]++;
            if (myArr[2] == checkArr[2])  check++;
            break;
        case 'T':
            myArr[3]++;
            if (myArr[3] == checkArr[3])  check++;
            break;
    }
}

void Remove(char c) { //제거할 문자를 처리하는 함수
    switch(c) {
        case 'A':
            if (myArr[0] == checkArr[0]) check--;
            myArr[0]--;
            break;
        case 'C':
            if (myArr[1] == checkArr[1]) check--;
            myArr[1]--;
            break;
        case 'G':
            if (myArr[2] == checkArr[2]) check--;
            myArr[2]--;
            break;
        case 'T':
            if (myArr[3] == checkArr[3]) check--;
            myArr[3]--;
            break;
    }
}

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

    int S, P;
    cin >> S >> P;
    int Result = 0;
    string A;
    cin >> A;

    for(int i=0;i<4;i++) {
        cin >> checkArr[i];
        if(checkArr[i] == 0) {
            check++;
        }
    }
    
    // 초기 윈도우: [0, P-1] 구간을 먼저 반영
    for(int i=0; i<P; i++) {
        Add(A[i]);
    }
    // 초기 윈도우가 4가지 조건을 모두 만족하면 결과 +1
    if(check == 4) {
        Result++;
    }

    //슬라이딩 윈도우 처리 부분
    for(int i=P; i<S; i++) {
        int j = i-P; // i: 새로 들어오는 문자의 인덱스, j: 빠져나가는 문자의 인덱스
        Add(A[i]);
        Remove(A[j]);
        if (check == 4) {
            Result++;
        }
    }
    cout << Result << "\n";
}

---

*이 글은 교재 "Do it! 알고리즘 코딩 테스트 C++" 기반으로 작성했습니다!