DEQUE 썸네일형 리스트형 BOJ)11003 최소값 찾기 문제: icpc.me/11003 구간 n에서 ai-l+1 ~ai의 최솟값을 매번 찍어내는 문제이다. RMQ 문제로 생각하여 세그트리나 multiset을 이용한 풀이를 예전에 제출했지만 n이 너무나도 커서 tle를 맞은 후 잊고 있던 문제였지만 오늘 다른 문제에서 다이나믹프로그래밍을 공부하다가 필요에 의해 다시 풀게 된 문제이다. 이 문제는 deque를 이용하여 해결할 수 있다. 연속 된 시퀀스에서 deque에는 pair형으로 해당 값과 해당 인덱스를 가지고 있을것이다. 우리는 답을 출력할 때 deque에 삽입 되어있는 구간에서 최솟값을 출력해야 하기때문에 앞이나 뒤에 최솟값을 가지고 있어야한다. 일단 deque의 front에 최솟값을 가지고 있다고 해보자. 그러면서 만약 deque의 front의 값의 인.. 더보기 BOJ)1021 회전하는 큐 문제: icpc.me/1021 주어진 순서대로 첫번째 원소를 뽑아 원하는 수를 뽑아낼 때 쉬프트 연산의 최소 횟수를 출력하는 문제이다. 쉬프트 연산은 앞 뒤에서 pop push가 가능한 deque을 이용하면 쉽게 해결가능하다 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include using namespace std;deque dq;int n, m, x, r;int main() { scanf("%d%d", &n, &m); for (int i = 1; i 더보기 이전 1 다음