배열의활용(투포인터_슬라이딩 윈도우)

DNA 비밀번호

https://www.acmicpc.net/problem/12891

파악

naive한 경우의 $O(N)$

$1 ≤ |P| ≤ |S| ≤ 1,000,000$ 인데, 문자열의 길이를 $S$, 부분 문자열을 $P$라 하였을 때에,
부분배열 P의 순회횟수($I$)는 $S-P+1$ 이다.

($s<5, p<5$)인 경우들을 나열 하였을 때 위와 같이 파악 가능

P가 1일 때의 순회횟수(I)는 S
P가 2일 때의 순회횟수(I)는 S-1
...
P가 n-1일 때의 순회횟수(I)는 2
P가 n일 때의 순회횟수는 1

총 연산횟수는 $I\times P$ 이다. (순회를 할 때마다 부분배열 P의 길이만큼 순회 하므로)
$P = S$로 총 연산횟수를 $S$에 대한 식으로 나타내면 ($-S^2+S+1$) 이므로, $P = \frac{1}{2}S$ 일 때 최대 값은$\frac{1}{4}S^2$

• 따라서 $O(N)$은 $N^2$이다.

(오답 요인) : Sliding_window_naivecase.cpp
naive한 경우에서 최악의 경우($P=\frac{1}{2}S$)를 살펴보지 못하였고,
부분배열 P의 순회횟수($I$)였을 때 P가 S에 따라 선형적으로 증가한다고 보고,
$P = \frac{1}{2}S$ 일 때를 고려하지 못해서 naive한 경우도 $O(N)=N$으로 보았다.

Counting array에 S--, E++

문제의 조건에서, 알파벳 개수 이상을 포함해야 한다고 하였고, 위의 naive한 경우에서는 Counting array의 겹치는 부분들을 계속해서 계산하고 있기에, Counting array에서 빠져 나가고, 새로 들어오는 부분만 계산

구상

데이터 입력

계수 배열 선언

• 초기 계수 배열은 ==P만큼 순회==한 후 조건 확인

    // (P)artArray(부분배열 최초 1회 순회)
    for (int i = 0; i < P; i++){ //부분배열만큼 돌려야 함...
        char ele = DNA[i];
        Update(ele, countArr, true);
    }

    // 초기 계수 배열 조건 확인
    int Check = CheckSeq(condition, countArr);
    DNASeqCount += Check;

• 그 이후엔 빠져나가는 값 (start = 0), 들어오는 값 (end = start+P(부분배열의 길이)) 만큼 순회
• 1회 포인터 전진(슬라이딩) 마다 조건 확인

    int start = 0; // 인덱스 유의
    int end = start + P; // 인덱스 유의

    while (end < S){
        Update(DNA[start], countArr, false);
        Update(DNA[end], countArr, true);
        int Check = CheckSeq(condition, countArr); // 조건 확인
        DNASeqCount += Check;
        start++;
        end++;
    }

사용 함수
Update : 배열 업데이트 함수

void Update(char ele, int countArr[], bool isAdd){
   int val = isAdd ? 1:-1;

   switch (ele){
       case 'A' : countArr[0] += val; break;
       case 'C' : countArr[1] += val; break;
       case 'G' : countArr[2] += val; break;
       case 'T' : countArr[3] += val; break;
   }

}

CheckSeq : 조건 확인 함수

int CheckSeq(int condition[], int countArr[]){
    
    for (int i = 0; i <4; i++){
        if (countArr[i] < condition[i]) {
            return 0;
        }
    }

    return 1;

---

최소값 찾기

https://www.acmicpc.net/problem/11003

파악

$D_{i} = A_{i-L+1}$ ~ $A_{i}$ 는 $L$까지는 $A_{1}, (A_{1}, A_{2}), (A_{1}, A_{2}, A_{3})...((A_{1}...A_{L}))$ 중의 최소값을 출력하고, 이후에는 범위에서의 첫번째 값을 빼고, 마지막 값을 집어넣어서 최소값을 갱신해야 한다.

1회 차에는 최소값을 구하는 범위를 특정하는 것이 어려워, 코드로 확인하였음

    int N, L;
    cin >> N >> L;
    
    for (int i = 1; i < N; i++){
        cout << i << "번째 일 때" << endl;
        for (int j = i-L+1; j <= i; j++){
            if (j <= 0){
                continue;
            }
            cout << j << ",";
        }
        cout << endl;
    }

시간 복잡도를 따지면, $L \times N$ 이고 문제의 조건에 따라 $L=N$ 이므로 최악의 경우는 $5\times 10^{12}$ 이므로 시간초과.

즉, L까지는 end_index를 더해주면서 min값만을 남기고, L 이후에는 인덱스를 판별해 새로 들어오는 min값과 비교해야 한다.

구상

L까지는 더하면서 비교

• (인덱스, 값)의 형태로 업데이트 해야 함
• min 값 하나만 남김

L 이후에는 인덱스를 고려해서 비교

인덱스와 값을 쌍으로 집어넣고 ==min값만을 남겨야 한다==는 점에서 deque 자료형을 사용해야 한다는 점을 인지

구현(deque를 활용)

deque 특징

• front, back 양쪽으로 삽입(front_push(), back_push()) 및 삭제(front_pop(), back_pop()) 가능
• 이번 코드에서는 first는 index, second는 value로 하였음(규정하기 나름)
• front에는 min 값이 있음

라이브러리

# include<iostream>
# include<deque>
# include <utility>
using namespace std;
typedef pair<int,int> Node; // std 이후로 선언해야 함

입력되는 now값 보다 큰 back 값 비교 $\rightarrow$ 삭제

        int now;
        cin >> now;
        // now 값을 dq에 더할 때
        while (dq.size() && (dq.back().second > now)){
            dq.pop_back(); //기존 값들 중 now 보다 큰값들을 다 버림
        }

now 값 입력

        dq.push_back(Node(i,now)); // 앞에 값들이 now 보다 작다면 남아있을 수 있음

인덱스 범위(i-L)를 넘어간 min값 제외

        // 인덱스 범위를 넘어간 min값 제외
        if (dq.front().first <= i-L){
            dq.pop_front();
        }

        cout << dq.front().second << " ";