기본 콘텐츠로 건너뛰기

11003 : 최소값 찾기 (Sliding Window) *미제

#include <iostream>
#include <vector>

using namespace std;

class SW
{
private:
vector<int> Saver;
int Index = 0;
public:
SW(int l);
void Updating(int input, int o_idx);
};

SW::SW(int l)
{
for (int j = 0; j < l; j++)
this->Saver.push_back(1000000000);
}

void SW::Updating(int input, int o_idx)
{
// 인덱스 초기화
this->Index %= this->Saver.size();

this->Saver[this->Index++] = input;

// 최솟값 찾기 - 최솟값만 저장하고 그것의 인덱스를 저장해놓고 그거랑 비교하다가 최솟값이 슬라이딩윈도우에서 사라지면 다시 최솟값을구한다?
                                                                                                         
int least = this->Saver[0];
for (int i = 1; i <= o_idx; i++)
{
if (least > this->Saver[i])
least = this->Saver[i];
}

// 최솟값 출력
cout << least << " ";
}

int main()
{
int N;
cin >> N;

int L;
cin >> L;

vector<int> D;
for (int i = 0; i < N; i++)
{
int Temp;
cin >> Temp;
D.push_back(Temp);
}

SW Practice(L);
for (int i = 0; i < N; i++)
{
if (i < L)
Practice.Updating(D[i], i);
else Practice.Updating(D[i], L - 1);

}

return 0;
}

댓글

이 블로그의 인기 게시물

11401 : 이항계수 3 (Dynamic Programming, Divide and Conquer) [C++]

1번, 2번 문제들과 확연히 차이나는 입력의 범위. 400만 ! DP를 사용해서 풀 수 없는 문제이다 . 하지만 DP가 쓰이긴 한다! 수학은 너무 어렵다. 곱셈의 역원을 공부해보다가 모르겠어서 도움을 구했다. 왜 곱셈의 역원을 구해야하는가? N! / (K! * (N-K)!) 에서 K! * (N-K)! 의 역원을 구해야 하기 때문! 곱셈의 역원을 구하는 정리인 페르마의 소정리를 이용하면 p가 1000000007 이지만 분할 정복을 이용한 제곱 수 계산 덕분에 logP 시간 소요. 분할 정복을 이용한 제곱 수 계산은 계속 써먹을 것 같아서 따로 올려놓았다. DP가 쓰이는 부분은 구해준 400만의 역원을 바탕으로 모든 역원을 구하는 부분이다. 그러므로 총 시간 소요는 O(N+LogP) long long BinomialCoefficient :: GetNum ( int N , int K ) { this - > Factorial [ 1 ] = 1 ; for ( int i = 2 ; i < = 4000000 ; i + + ) this - > Factorial [ i ] = ( this - > Factorial [ i - 1 ] * i ) % P ; this - > Invert [ 4000000 ] = this - > Pow_DC ( this - > Factorial [ 4000000 ] , P - 2 ) ; for ( int i = 4000000 - 1 ; i > 0 ; i - - ) this - > Invert [ i ] = ( this - > Invert [ i + 1 ] * ( i + 1 ) ) % P ; if ( N = = K | | K = ...

1978 : 소수 찾기 [C++]

# include < iostream > # include < vector > using namespace std ; int main ( ) { cin . tie ( NULL ) ; vector < int > Primes ; Primes . push_back ( 2 ) ; Primes . push_back ( 3 ) ; for ( int i = 4 ; i < 1000 ; i + + ) { bool IsPrime = true ; if ( i % 2 = = 0 | | i % 3 = = 0 ) continue ; for ( int j = 4 ; j < i ; j + + ) { if ( i % j = = 0 ) { IsPrime = false ; break ; } } if ( IsPrime ) Primes . push_back ( i ) ; } int N , Count = 0 ; cin > > N ; for ( int i = 0 ; i < N ; i + + ) { int Input ; cin > > Input ; for ( int j = 0 ; j < Primes . size ( ) ; j + + ) if ( Input = = Primes [ j ] ) Count + + ; } cout < < Count < < " \n " ; return 0 ; }