기본 콘텐츠로 건너뛰기

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;
}

댓글

이 블로그의 인기 게시물

6359 : 만취한 상범 (Dynamic Programming) [C++]

# include < iostream > # include < vector > using namespace std ; int Num_of_Divisor ( int n ) { int Count = 0 ; for ( int i = 1 ; i < = n ; i + + ) if ( n % i = = 0 ) Count + + ; return Count ; } int main ( ) { int Testcase ; cin > > Testcase ; while ( Testcase - - ) { int Rooms ; cin > > Rooms ; vector < int > Prisons ; for ( int i = 0 ; i < Rooms ; i + + ) Prisons . push_back ( 0 ) ; for ( int i = 1 ; i < Prisons . size ( ) + 1 ; i + + ) { if ( ( Num_of_Divisor ( i ) % 2 ) = = 0 ) Prisons [ i - 1 ] = 0 ; else Prisons [ i - 1 ] = 1 ; } int Fleer = 0 ; for ( int i = 0 ; i < Prisons . size ( ) ; i + + ) if ( Prisons ...

11004 : K번째 수 [C++]

# include < iostream > # include < cstdio > # include < algorithm > int main ( ) { int * Number = new int [ 5000000 ] ; int N , K ; scanf ( " %d %d " , & N , & K ) ; for ( int i = 0 ; i < N ; i + + ) scanf ( " %d " , Number [ i ] ) ; std :: sort ( Number , Number + N ) ; printf ( " %d " , Number [ K - 1 ] ) ; return 0 ; }

1149 : RGB Street Coloring (Dynamic Programming) [C,C++]

The key to this problem lies in understanding the principles. Let me explain the algorithm to solve the problem by using DP. First, you need the same storage space like input data's size. When you draw any color of the nth house, the space will contain the minimum value. If you paint the red in the second house, this value is sum of blue or green of the first house.  You must use DP because you must use the previous value.  Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.  If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.  Therefore, the minimum value can be found in the value of the storage space (n-1) index. <pesudo code> *Source of the problem =  https://www.acmicpc.net/problem/1149 *문제 출처 : BAEKJOON ONLINE JUDGE