본문 바로가기
반응형

Segment Tree

[BOJ 20190] 버블버블 [문제] www.acmicpc.net/problem/20190 20190번: 버블버블 여러분은 N개의 정수 A1, · · · , AN을 버블 정렬(bubble sort)를 이용하여 단조증가하도록 (감소하지 않는 순서가 되도록) 정렬하려고 한다. 주어진 정수들 중에는 같은 값이 있을 수 있다. 버블 정렬 www.acmicpc.net [난이도] - Platinum II (20.12.28 기준) [필요 개념] - Lazy Propagation - Segment Tree / Fenwick Tree [풀이] 올해 koi 중등부 2차 문제이다. 중등부에 이런 난이도 문제가 나온다는 거에 한 번 놀랐고, 이 문제 만점자가 4명이나 된다는 거에 두 번 놀랐다. 이 문제를 보고 lazy propagation을 떠올리기도..
[알고리즘] Lazy Propagation (Segment / Fenwick Tree) [목차] 1. Lazy Propagation이란? 2. Lazy Propagation with Segment Tree 3. Lazy Propagation with Fenwick Tree 4. Lazy Propagation 예시 문제 1. Lazy Propagation이란? 혹시 세그먼트 트리(Segment Tree)와 펜윅 트리(Fenwick Tree)에 대해서 잘 모른다면 이 자료구조들에 대해서 학습한 후, 이 글을 보는 것을 권장한다. 세그먼트 트리나 펜윅 트리는 원소의 update가 있는 경우에 구간합을 빠르게 구해주기 위해서 사용한다. 한 원소의 update는 O(logN)만큼의 시간이 걸리고, 구간합 또한 O(logN)만큼의 시간이 걸리기 때문에 Q를 쿼리의 개수라고 하면 보통 O(QlogN) ..
[BOJ 17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 [문제] www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net [난이도] - Platinum II (solved.ac 20.12.22 기준) [필요 개념] - Lazy Propagation with Segment Tree - Fenwick Tree 디스크립션은 간단하다. 두 종류의 쿼리가 들어오고, 한 쿼리는 구간 [L, R]에 순서대로 1, 2, ..., R-L+1을 더해준다. 나머지 한 쿼리는 X번째 원소의 값을 출력해준..
[BOJ 2336] 굉장한 학생 [문제] : https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 문제 N명의 학생이 참여하여 세 번의 시험을 치렀다. N명의 학생들은 세 번의 시험에 모두 응시하였다. 조교는 각각의 시험에서 같은 등수의 학생이 한 명도 없도록 성적을 매겼다. A라는 학생이 www.acmicpc.net [난이도] - Platinum 2 (2020.08.05 solved.ac 기준) [개념] - 세그먼트 트리 (Segment Tree) [풀이] 우선 https://jason9319.tistory.com/57 블로그의 설명을 참고하여 풀이를 하였다. 문제를 요약하자면, 각 학생이 세 번의 시험에 참여하였고, 학생 A보다 세 과목이 모두 더 높은 등수인 사람이 없다면 A를 '굉장하다'라고..
[BOJ 2517] 달리기 출처 : https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다. www.acmicpc.net 세그먼트 트리(Segment Tree)를 이용한 문제이다. 각 선수마다 자기보다 앞에 달리고 있는 선수들 중에서 자신보다 실력이 높은 사람의 수 + 1이 자신의 최선의 등수가 된다. 각 선수들의 실력을 정수로 나타내었고, 실력의 범위가 1~10억이다. 여기..

티스토리툴바