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로 구현하되, ..

목차 Solution 1. 선형 탐색 Solution 2. 세그먼트 트리 1) 생성하기 (Initialization) 2) 검색하기 (Search) 3) 수정하기 (Update) 예제) BOJ 2042 세그먼트 트리(Segment tree)는 어떤 수열들의 특정 구간에 대한 부분합, 최소값, 최대값 등을 쉽게 구하기 위하여 사용하는 자료구조 입니다. 보통 부분합, 최소값 등을 구하고자 하는 질의(query)가 여러 번 있을 때 사용합니다. 예를 들어, 배열(int arr[12])에 다음과 같은 값들이 있다고 가정하고 arr[1]~arr[8]의 부분합을 구해보죠. int arr[12] = {10, 7, 9, 0, 11, 7, 6, 5, 2, 13, 8, 6, 9}; Solution 1. 선형 탐색 구간 1..

목차 문제 풀이 코드 보기 문제 풀이 구간 합 구하기의 응용 버전입니다. 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연산을 해주지 않았다고 생각..