세그먼트 트리
-
BOJ) 최솟값과 최댓값 (2357 번)알고리즘/백준 2021. 1. 5. 18:24
최솟값과 최댓값 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 앞서 포스팅한 세그먼트 트리를 활용하는 문제다. 위의 문제와 차이점이라면 구간 합을 구하는 대신, 최솟값과 최댓값을 저장한다는 점이다. 또한, 이 문제에서는 세그먼트 트리의 크기를 직접 구해서 초기화해줬다. 세그먼트 트리 초기화 private static class SegmentTree { int[] minTree, maxTree, numArr; private int size; public SegmentTre..
-
BOJ) 구간 합 구하기 (2042 번)알고리즘/백준 2021. 1. 5. 18:09
구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리를 이용해서 푸는 문제다. 우선, 이 문제를 풀기 위해서 세그먼트 트리에 대해서 공부해야했다. 백준 사이트에 블로그란에 기재되어있는 세그먼트 트리를 보고 풀었다. 세그먼트 트리란 무엇인가?? 먼저, 세그먼트 트리는 배열의 크기가 커질 경우, 연산 식에 유용하다. 공간 복잡도가 O(N^2)이고 시간 복잡도가 O(N^2)인 배열에 대한 연산이 있다면, 세그먼트 트리를 이용하여 O..