문제 링크 http://icpc.me/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 덱을 이용하여 풀 수 있다. 덱에 들어있는 값을 단조적으로 유지하면서 k번째 값이 들어올 때 그 k번째 값이 덱에서 가장 큰 값을 유지하게 덱을 관리하면 된다. 또한 덱에는 k - l - 1 이후에 들어온 값만 있어야 한다. 덱을 위와 같이 관리하면 덱의 제일 앞에 있는 값이 최솟값이 되게 된다. cf) 세그먼트 트리를 이용하면 O(nlogn)에 풀 수 있을 것 같지만 상수 때문..

문제 링크 http://icpc.me/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 덱을 이용하여 풀이 할 수 있다. 배열을 뒤집을 때, 진짜로 배열을 뒤집게 된다면 이때 시간복잡도가 O(n)이기 때문에 O(np)가 되어 터지게 된다. 그렇기 때문에 배열을 뒤집었는지 여부를 체크하여 수를 앞에서 버릴지 뒤에서 버릴지 정해야한다. 코드 #include #include #include using namespace std; void solve() { deque dq; string cmd; cin >> cmd; int n; cin >> n; string i..

문제 링크 http://icpc.me/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 덱을 이용하여 풀 수 있다. 덱에서 뽑을 수의 위치를 찾아서 그 위치가 덱의 중간지점보다 오른쪽에 있다면 3번을 덱의 첫 번째에 원하는 수가 위치할 때까지 반복하고, 중간지점보다 왼쪽에 있다면 2번을 첫 번째에 원하는 수가 위치할 때까지 반복한다. 코드 #include #include #include using namespace std; int main() { deque dq; int n, m; scanf(..