본문 바로가기
728x90

세그먼트 트리3

[JAVA]백준 2357번: 최솟값과 최댓값 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 1. 문제 설명 N개의 정수들이 주어지고 a,b 쌍이 M개 주어질때 a번째부터 b번째까지 정수의 최소, 최댓값 출력 2. 풀이 간단한 인덱스(세그먼트)트리 문제이다. 부분합 대신 최댓값, 최솟값만 저장해서 update, query를 진행하면 된다. *로직 - 정수를 입력 받는다. - 입력받은 정수로 minTree(최솟값 저장), maxTree(최댓값 저장)를 .. 2021. 8. 2.
[JAVA]백준 2094번: 강수량 https://www.acmicpc.net/problem/2094 2094번: 강수량 첫째 줄에 정수 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 n개의 줄에는 두 정수 y(0 ≤ |y| ≤ 1,000,000,000), r(1 ≤ r ≤ 1,000,000,000)이 주어지는데, 이는 y년도의 강수량이 r이라는 의미이다. 이러한 정보는 y www.acmicpc.net 1. 문제 설명 X 년도에는 Y 년도 이후 가장 많은 비가 내렸다 라고 말하려면 3가지 조건이 만족해야 한다. 1. Y 년도, X 년도, 그리고 그 사이의 모든 년도들의 강수량에 대한 정보가 알려져 있다. 2. X년도의 강수량은 Y 년도의 강수량 이하이다. 3. Y < Z < X를 만족하는 모든 Z에 대해서, Z 년도의 강수량은 X 년도.. 2021. 7. 28.
[JAVA]백준 1725번: 히스토그램 www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 1. 문제 설명 주어진 히스토그램에 대해 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하는 문제이다. 종만북의 분할 정복 예시 문제 울타리 잘라내기 문제와 같은 문제이다. 종만북의 풀이과정 같이 3가지의 형태로 문제를 분할하여서 풀었다. 막대그래프를 반으로 잘랐을 때 가장 큰 직사각형은 3가지의 경우로 존재할 수 있다. 1. 가장 큰 직사각형은 왼쪽 그래프에만 있을 경우 2. 가.. 2021. 1. 2.
728x90

티스토리툴바