슬라이딩 윈도우

n의 크기로 문제 풀이를 대충 예측할 수 있음

N이 10이나 15 정도라면 재귀를 먼저 생각하고 50~100 정도에서 최솟값을 요구한다면 BFS로 접근해본다.

그러나 n이 100000 처럼 매우 크다면 1중 for문으로 해결해야 한다.

 

포인터는 8bytes

 

main 함수의 메모리 크기(스택)가 작으므로 10만개가 넘어가면 안전하게 전역으로 선언해주는 것이 좋다.

 

메모리는 하지 말아야할 것을 말해줌

보통 256메가 바이트이므로 문제 풀이할 때 10000*10000 배열 설계시 잘못 설계한 것

 

 

슬라이딩 윈도우

 

O(n)의 시간복잡도를 가짐

 

#include <iostream>
using namespace std;
int arr[11] = {4, 5, 1, 1, 5, 4, -3, -13, 9, 20, 13};
int num = 0;
int slidingWindow(int index)
{
    
    if(index == 0)
    {
        for(int i=0; i<5; i++)
            num += arr[i];
    }
    else
    {
        num -= arr[index-1];
        num += arr[index+4];
    }
    return num;
}
int main()
{
    for(int i=0; i<7; i++)
    {
        cout << slidingWindow(i) << ' ';
    }
    
    return 0;
}

 

슬라이딩 윈도우는 경계값을 조심해주어야 한다.

 

 

string 클래스는 사실 슬라이딩 윈도우로 작성해도 속도의 이점이 없지만 익숙해지기 위해서 사용해봄

#include <iostream>
#include <string>
using namespace std;
string path = "ABABTABCABABAACD";

int getSum()
{
    string tar = path.substr(0, 3);
    int cnt = 0;
    int limit = path.length() - 3;
    for(int i=0; i<=limit; i++)
    {
        if(tar == "ABA")
            cnt++;
        
        if(limit == i) break;
        tar.erase(0, 1);
        tar += path[i+tar.length()];
    }
    return cnt;
}
int main()
{
    int ret = getSum();
    cout << ret;
    return 0;
}

 

#include <iostream>
using namespace std;
int arr[15] = {4, 5, 6, 1, 1, 3, 2, 6, 9, 1, 1, 2, 0, 3, 2};

int getNum(int size)
{
    int num = 0;
    for(int i=0; i < size; i++)
        num += arr[i];
    
    return num;
}

int getLargeSize(int size)
{
    int temp = getNum(size);
    for(int i=0; i<=15-size; i++)
    {
        if(temp == 7)
            return 1;
        if(i == 15 - size) break;
        temp -= arr[i];
        temp += arr[i + size];
    }
    
    return 0;
}
int main()
{
    for(int i=15; i>0; i--)
    {
        if(getLargeSize(i) == 1)
        {
            cout << i;
            break;
        }
    }
    return 0;
}

 

전체를 5조각으로 잘랐을 때 가장 동일 알파벳이 많은 경우 그 갯수와 해당 알파벳 출력

#include <iostream>
#include <string>
using namespace std;
string name = "BAQRRGGVAQZAACT";
int dat[200], maxNum = -1e9;
char maxCh;

void slide()
{
    for(int i=0; i<5; i++)
    {
        dat[name[i]]++;
        if(maxNum < dat[name[i]])
        {
            maxNum = dat[name[i]];
            maxCh = name[i];
        }
    }
    int limit = name.length() - 5;
    for(int i=0; i<=limit; i++)
    {
        if(limit == i) break;
        
        dat[name[i]]--;
        dat[name[i+5]]++;
        if(maxNum < dat[name[i+5]])
        {
            maxNum = dat[name[i+5]];
            maxCh = name[i+5];
        }
    }
}

int main()
{
    slide();
    cout << maxNum << ' ' << maxCh;
    return 0;
}