Study Log

문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 설계 주어진 입력의 개수는 최대 100,000개이고, 주어진 시간은 1초이다. 따라서 이 문제는 최소 $ O(n \mathrm{log}n) $의 시간복잡도로 해결해야 한다. 입력을 하는 과정에서 n번의 연산을 하는 것은 어쩔 수 없으니, 저번과 같이 답을 구하는 과정에서 $O(1)$의 시간이 걸리는 큐나 덱을 사용해보자. 여기서 포인트는 데이터를 절댓값 순으로 정렬해야한..

문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 설계 N개의 수가 주어지고, 숫자 L이 주어지며 주어진 $D_{i}$ 의 최솟값들을 출력하는 문제이다. 기본적인 구성은 위의 그림과 같다. L = 2일 때, $D_{i}$ 는 $A_{i-1}$ ~ $A_{i}$ 의 범위 중 최솟값이 되고, L = 3일 때, $D_{i}$ 는 $A_{i-2}$ ~ $A_{i}$ 의 범위 중 최솟값이 된다. 이를 알아보기 쉽게 표..