Byeo

목차 개요 설명 한계 코드 개요 해당 문제는 배열이 주어져 있을 때, 특정 부분의 구간 합을 구하는 문제입니다. 눈여겨 볼 것은 배열이 주어지고 난 뒤, 배열 값이 변하지 않는다는 사실입니다. 이 문제는 첫 index부터 마지막 index까지 부분합을 모두 계산한 뒤, 결과를 저장해서 빼기 연산으로 쉽게 풀 수 있습니다. 즉, DP 문제입니다. 설명 5 3 5 4 3 2 1 1 3 2 4 5 5 백준 예제로 방법을 간단하게 보겠습니다. 배열의 원소 5, 4, 3, 2, 1로 들어온 값을 arr에 저장해 둡시다. 그리고 0번 ~ i번 까지의 배열 합을 sum[i]에 저장해 놓도록 하죠. 처음 sum[0] 은 단순히 arr[0]이 되겠죠. 이제 다음부터 sum[1]은 arr[1] + sum[0], ... s..

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연산을 해주지 않았다고 생각..