Byeo

boj 12899 - 데이터 구조 목차 개요 설명 코드 개요 이 문제는 Binary search 과정과 유사한 문제입니다. 다만, "X보다 작은 수는 몇 개 있는가?" 를 쉽게 알아내기 위하여, 이 과정에서 부분 합 segment tree를 사용합니다. 먼저, 2,000,000개의 배열을 관리할 수 있는 segment tree를 구성합니다. 1번 query 가 들어온 경우 : 요청 값을 a라 했을 때, a를 담당하는 leaf 노드를 찾아 그 값에 +1을 해준 뒤 순차적으로 root node까지 update해나갑니다. 2번 query 가 들어온 경우 : 이는 binary search와 유사합니다. Child node 두 개를 살펴 본 뒤에, 내가 몇 번째 원소를 찾느냐에 따라 왼쪽 혹은 오른쪽 중 하나만 ..

boj 9345 목차 개요 설명 코드 개요 boj 9345 - 디지털 비디오 디스크(DVDs) 문제도 segment tree를 응용한 문제입니다. Query 0 이 들어왔을 때는 DVD 배열에서 a번째와 b번째의 값을 바꿔주면 되고, Query 1이 들어왔을 때는 a ~ b 의 구간을 검색하면 됩니다. 얼핏 보기에는 segment tree를 어떻게 응용해야 하는 지에 대해 의문이 들 수 있습니다. 하지만 잘 살펴보면, Query 1이 들어왔을 때는 "a ~ b 의 구간에서 DVD가 a번부터 b번까지 모두 존재하는가" 를 살펴 보면 됩니다. 문제를 바꾸면, a ~ b 구간에서 중간 DVD를 살펴 볼 필요 없이 최솟값과 최댓값을 살펴보면 됩니다. 즉, a ~ b 구간의 최솟값이 a이면서, 최댓값이 b라면 조..

BOJ 2357 - 최솟값과 최댓값 목차 설명 code 이 문제는 segment tree를 변형하면 해결할 수 있는 문제입니다. 기존에 child의 부분 합을 저장했다면, 이 문제에서는 child의 최소값과 최대값을 저장하면 됩니다. Segment tree에 대한 설명은 [세그먼트 트리(Segment tree)]에서 볼 수 있습니다. 설명 BOJ 2357의 예제를 그대로 그려보면 다음과 같은 segment tree를 그릴 수 있을 것입니다! Maximum Segment Tree Minimum Segment Tree 18 ~ 23, 25 ~ 32 node는 segment tree의 코드를 따라 구현하면 관련이 없는 leaf ndoe입니다. Code 1. 코드의 깔끔함을 위하여 같은 class로 구현하되, ..

목차 문제 풀이 코드 보기 문제 풀이 구간 합 구하기의 응용 버전입니다. Segment tree에 관한 설명은 다음 게시글을 참조하면 됩니다. 세그먼트 트리, BOJ2042 BOJ 2042에서는 각 노드에 구간 합을 저장했다면 이번에는 구간 곱을 저장하면 됩니다. ※ Check List! 매 계산할 때마다 1,000,000,007로 나눠야 합니다. 더하기와는 다르게 어떤 수 a와 b를 곱할 때 1,000,000,007 보다 작은 수를 곱하게 되겠죠. 그런데 이 값은 Integer를 초과합니다. 따라서 중간 과정은 모두 long type이어야 합니다. 빨간색으로 칠해진 node는 모두 1,000,000,007을 넘겨 modular 연산된 숫자들입니다. 만약, 저기서 modular연산을 해주지 않았다고 생각..