[백준 11003] 최솟값 찾기

[ghdcksgml1]

컴퓨터구조론 공부하다가 너무 재미없어서 재밌는 알고리즘을 풀었다.

- 문제 아이디어

이 문제는 증가하는 구간의 최솟값을 구하는 비교적 간단한(?) 문제이다.

이 문제를 보고 세그먼트 트리 아니면 슬라이딩 윈도우를 통해 풀 수 있을 것 같았다.

그래서 가장 익숙한 세그먼트 트리로 풀었는데, 20%에서 시간 초과가 나서 슬라이딩 윈도우로 풀었다. ㅜ ( 아마 N <= 5,000,000이라 logN이 꽤 커서 시간초과가 난듯하다.)

다음과 같은 원리로 풀었다. 자료구조는 덱을 사용하여

루프를 돌면서 {값,인덱스}를 넣어준다. 그러면서, 덱의 맨앞의 인덱스가 i-L보다 작거나 같은게 있으면 없애주고(덱에 A_i-L+1 ~ A_i값만 넣어주기 위해),

그러면서 덱의 맨 마지막 값이 현재 arr값보다 작은게 있으면 모두 삭제한다.

이렇게 되면, A_i-L+1 ~ A_i의 최솟값이 덱의 맨 앞에있고, 덱의 앞부분을 지워도 다음 최솟값이 나오게 만들어줄 수 있다.

- 소스코드

세그먼트 트리 ( 시간초과 )

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset
#define MAX 5000001

using namespace std;

struct Tree{
    int mn;
}tree[MAX*4];

int arr[MAX];

int buildRec(int node,int start,int end){
    if(start == end){
        return tree[node].mn = arr[start];
    }
    int mid = (start + end) / 2;
    return tree[node].mn = min(buildRec(node*2,start,mid), buildRec(node*2+1,mid+1,end));
}

int queryRec(int left,int right,int node,int start,int end){
    if(left>end || right<start) return 1000000001;
    if(left<=start && end<=right){
        return tree[node].mn;
    }
    int mid = (start + end) / 2;
    return min(queryRec(left,right,node*2,start,mid), queryRec(left,right,node*2+1,mid+1,end));
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N; cin>>N;
    int L; cin>>L;
    for(int i=1;i<=N;i++){
        cin>>arr[i];
    }

    buildRec(1,1,N);

    for(int i=1;i<=N;i++){
        int tmp = (i-L+1)>0 ? i-L+1 : 1;
        cout<<queryRec(tmp,i,1,1,N)<<' ';
    }

    return 0;
}

슬라이딩 윈도우 (성공)

// 언어 : C++ , (성공/실패) : 1/2 , 메모리 : 63120 KB , 시간 : 1396ms
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <string.h> // memset
#define MAX 5000000

using namespace std;

int arr[MAX];
deque<pair<int,int>> dq;

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int N,L;
    cin>>N>>L;

    for(int i=0;i<N;i++) cin>>arr[i];

    for(int i=0;i<N;i++){
        // 인덱스가 i-L보다 작거나 같은게 있으면 없애준다.
        while(!dq.empty() && dq.front().second <= i-L)
            dq.pop_front();

        // 현재 arr값보다 dq.back()의 값이 더 크다면 없애준다.
        while(!dq.empty() && dq.back().first > arr[i])
            dq.pop_back();

        dq.push_back({arr[i],i});
        cout<<dq.front().first<<' ';
    }

    return 0;
}

gimoZZi

[jusung-c]

gimoZZi !!

[BanApp]

바보 같은 난 눈물이 날까 ~

[ghdcksgml1]

결국 컴구시험은 잘 쳤는데 시험시간 3시간 반 레전드였습니다. ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

[BanApp]

ㄹㅇ?ㅋㅋㅋㅋㅋㅋ 난이도 어땠습니까,,