10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 분석 세그먼트 트리, 인덱스 트리, 구간합 1. 세그먼트 트리 주어진 데이터의 구간합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조 2. 구간합 합배열(prefix sum)은 업데이트가 느림 arr[1]를 update 한다면 ? sum[1]부터 sum[9]까지 karla.tistory.com 풀이 """ N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를..

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 분석 일정 법위에서 최솟값을 찾는 문제 : 슬라이딩 윈도우/ 정렬 정렬 N과 L의 범위가 5,000,000인 문제에서 정렬 사용 불가 슬라이딩 윈도우 덱으로 구현하여 정렬 효과 i-L+1 ~ i 까지 이므로 윈도우 크기는 L로 생각 예시 N: 12, L : 3, A: 1 5 2 3 6 2 3 7 3 5 2 6 1. 새 노드 (3,2)가 저장될 때 뒤에서부터 비교 시작 : (2,5)는 (3,2)보다 숫자가 크므로 덱에서 제거 (최솟값..