# 세그먼트트리

6개의 포스트

[알고리즘] 백준 > #3745. 오름세

\[백준 문제를 읽고 \[백준 > \`\`\`class Solution3745 {}class Stock implements Comparable { int index; int price;}

2021년 3월 18일
·
0개의 댓글

[알고리즘] 백준 > #12015. 가장 긴 증가하는 부분 수열 2

와 굉장히 어려웠다\[백준 어려운 문제였다. 세그먼트 트리를 사용해 문제를 해결했는데, 세그먼트트리를 사용해야한다고 생각하는 과정도 어려웠고 시간초과가 나서 그걸 해결하는것도 힘들었다 -0-일단, 세그먼트트리 아이디어를 얻은 과정은 다음과 같다. 이 문제는 dp로도 풀

2021년 2월 17일
·
0개의 댓글
post-thumbnail

BOJ_6549_히스토그램에서 가장 큰 직사각형

6549 - 히스토그램에서 가장 큰 직사각형 N의 범위가 100,000 이하 이므로 최소한 O(NlogN) 의 시간복잡도를 가져야 한다. 정렬 ? 하면 문제 자체의 의미가 없으므로 패스 높이를 기준으로 풀면 O(NM) 이 이미 1초를 훨씬넘기므로 패스 단순히 문제 자체가 요구하는 바는 넓이의 최댓값.. (질의) 그리고 O(NlogN) 의 시간...

2020년 12월 19일
·
0개의 댓글
post-thumbnail

Segment Tree 자료구조 - 구간에 대한 Update/Query

세그먼트 트리는 인덱스 트리와 비슷한 구조를 가지지만, 추가적인 공간을 활용하여 좀 더 복잡한 형태의 대표값(0이 아닌 값, 1인 비트의 수, 등)을 표현할 수 있을 뿐만 아니라 가장 큰 차이점은 동시에 구간적인 변화가 일어나도 이를 O(log2(N))만에 처리가 가능

2020년 9월 2일
·
0개의 댓글

백준 2042번: 구간 합 구하기

문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리

2020년 8월 27일
·
0개의 댓글