Segment Tree

Segment Tree > 구간 사이의 정보를 저장하는 tree 문제 가정 아래의 문제를 생각해 보자. size가 n인 array가 있을 때, 두 가지 operation이 가능하다. query: l부터 r까지의 모든 값을 더하기 ( 0 <= l <= r <= n -

updates를 미루면서, 구간 updates를 최적화 시키는 알고리즘위의 그림은, 구간의 합을 저장하는 Segment Tree이다. 이를 통해서, 하나의 값뿐만 아니라, 동시에 구간의 합도 O(logN)이라는 빠른 시간 안에 update 할 수 있다.그러나, 값 하나

시간 제한: 1초메모리 제한: 256MB 구간에 대한 많은 Update와 Query를 수행해야 하는 문제이다.Segment Tree를 이용할 수 있을 것이다.딱 일반적인 Segment Tree처럼 구현하면 된다.ST를 담기 위한 Array가 필요하다.height = c

문제 시간 제한: 1초 메모리 제한: 256MB Problem Analysis 실제로 DVD를 중간에서 빼내 위에 올려놓는 것처럼 구현하기 위해서는, DVD를 찾는 것부터, 위에 있는 것들을 한 칸씩 내리는 것까지, 해결해야 할 문제들이 있다. Algorithm

시간 제한: 0.5초메모리 제한: 512MBNaive한 방법은, i부터 j까지 순서대로 stack을 이용하여 top에 '('가 있을 때 ')'이 다음으로 오면 pop을 하고, 그 외에는 계속 push를 해주면서, 마지막에 stack이 비었다면 올바른 문자열로 판단하는

시간 제한: 1초메모리 제한: 256MB많은 부하를 빠르게 갱신해야 하는데, naive 하게 풀면 최대 O(N)이다. lazy propagation을 이용하면 O(logN)으로 줄일 수 있을 것이다. 그런데 문제는, 부하의 범위가 연속적이지 않을 수 있다는 점이다. 부

시간 제한: 1초메모리 제한: 256MBNaive 하게 풀면, 매번 K 구간에 있는 수들을 정렬하여 (k+1)/2번째 수를 얻을 수 있다. 이 방법은, O(KlogK)를 N-k+1번 반복하게 되므로 시간 복잡도가 너무 크다. 그러나, K 크기의 창을 한 칸씩 옮기는 동

시간 제한: 2초메모리 제한: 128MBNaive 하게 풀면, 매번 각 순서를 정렬하여 답을 구할 수 있다. 이러한 방법은 시간 복잡도 차원에서 큰 부담이 된다. 대신에, 어떤 행동을 취할 때 상자에 계속 유지되고 있는 사탕들을 계속 정렬해 줄 필요는 없을 것이므로,

업로드중..시간 제한: 1초메모리 제한:: 256MBNaive하게 풀면, 매번 각 선수의 앞에서 달리고 있는 선수들의 실력을 조사하여 최선의 등수를 구할 수 있다. 그러나, 이는 시간 복잡도가 O(N^2)이다. 앞에 특저 선수가 존재하는 걸 이미 알고 있는데 매번 다시

시간 제한: 2초메모리 제한: 192MBNaive 하게 풀면, C(N, 2) 가지의 모든 경우를 비교하여 풀 수 있다. 그러나, 이는 시간 복잡도가 O(N^2)이다. 간단하게 두 번의 시험만 친다고 하면, 첫 시험에서 자신보다 잘 본 사람만 두 번째 시험 점수를 확인하

시간 제한: 1초메모리 제한: 512MBAi보다 작은 값이 Ai+1, ...., N-1 중에 k 개가 있다면 k 번 swap 해야 한다. 각 i 별로 K를 모두 구해 합해주면 된다. 이때, 매번 Naive 하게 수를 비교하면 O(N^2)이 된다. 대신에, Segment

시간 제한: 256MB메모리 제한: 1초Naive 하게 풀면, N(N-1) 가지 쌍을 모두 조사하면 되지만 오래 걸린다. 대신, Segment Tree로 원하는 범위에 존재하는 섬을 조사할 수 있다면, 시간을 단축시킬 수 있을 것이다.남쪽 섬부터 시작해서 북쪽 섬 순서

시간 제한: 0.5초메모리 제한: 512MB이처럼, ai 만큼 앞에 빈칸을 둔 자리에 i를 배치하면, 문제를 해결할 수 있다. 이때 빈칸을 Naive 하게 세면 O(N^2)이 걸린다. 이를 개선하기 위해, Segment Tree를 이용하면, 구간의 크기를 쉽게 구할 수

시간 제한: 1초메모리 제한: 256MB이 문제는 기본적인 Segment Tree 개념을 기반으로, 2D Segment Tree를 구현해야 한다.column을 기준으로 각 범위마다, row 기준 ST를 갖도록 만든다.이후, update와 getSum을 column 기준

시간 제한: 1초메모리 제한: 512MB각 cell 별로 종이의 수를 구하고, 범위 내에서 최대를 빠르게 구하기 위해 Segment Tree를 이용하면 된다.그러나, Navie 하게 색종이가 주어질 때마다 위와 같이 해당 영역에 값을 더하면, 전처리 과정에서만 너무 많