-
BOJ 2357 최솟값과 최댓값Problem_Solving 2020. 2. 1. 20:42
1. 문제 설명
N 개의 정수가 주어지고 M개 구간 a와 b가 주어질 때 구간 [a,b]의 최소값과 최대값을 구하는 문제
2.풀이 방법
1) Segment Tree를 이용 하여 구한다.
2) 코딩을 간단하게 하기위해 최소 값 또는 최대값 세그먼트를 구현한뒤 트리를 빌드 할 때 -1를 곱한다.3.세그먼트 트리 설명
Divide : input으로 들어온 데이터를 반으로 나눈다.
Conquer : Divide에서 나누어진 Sub Array A[1...mid] B[mid...N] 의 최소값 또는 최대값을 재귀 적으로 구한다.
Combine : 두개로 나누어지 배열에 A, B에서 최소값을 리턴받아 해당 노드에 저장
- 노드에 적혀 있는 번호가 배열의 인덱스 번호
- 해당 구간은 리턴되는 값
만약 N개의 숫자가 있고 segment 트리를 구축 할 때 배열을 반으로 나누어 가면서 단말노드(배열 원소가 1개 남을때)에 도달 할 때까지 반복하여 최소값 또는 최대값을 리턴한다.
Golang 으로 짜여진 코드
'Problem_Solving' 카테고리의 다른 글
BOJ 9934 완전 이진 트리 (0) 2020.02.02 Codeforce #521 Div3 D. Cutting Out (0) 2018.11.18 Codeforce #521 Div3 E. Thematic Contests (0) 2018.11.18 Array Manipulation (0) 2018.11.11 Codeforce #515 Binary Numbers AND Sum (0) 2018.10.28 댓글