본문 바로가기

Algorithm/Segment Tree

 (7)
(C++) - 백준(BOJ) 12837번 : 가계부 (Hard) https://www.acmicpc.net/problem/12837 12837번: 가계부 (Hard) 살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 www.acmicpc.net segment tree문제였습니다. 📕 풀이방법 📔 입력 및 초기화 기존의 값들은 모두 0에서 출발하므로 init을 만들 필요가 없습니다. 따라서 쿼리의 개수만큼 a,b,c라는 변수에 입력받습니다. 📔 풀이과정 1. a==1 이면 update함수를 수행합니다. 이는 변화값을 따로 계산해서 그 차이만큼만 해당하는 구간에 더해주는 것이 아니며 그저 더해주기만 하면 됩니다. 2. a==2이면 b ~ c까..
(C++) - 백준(BOJ) 14428번 : 수열과 쿼리 16 https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 www.acmicpc.net segment tree로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 가장 작은 값, 그 중에서 가장 작은 인덱스를 뽑아야 하기 때문에 struct Node를 선언해 바로 index를 뽑을 수 있도록 변수들을 선언했습니다. 또한 min함수를 struct에 대해 사용하기 위해 연산자 오버로딩(함수 중복정의) 을..
(C++) - 백준(BOJ) 14427번 : 수열과 쿼리 15 https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net segment tree로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 가장 작은 값, 그 중에서 가장 작은 인덱스를 뽑아야 하기 때문에 struct Node를 선언해 바로 index를 뽑을 수 있도록 변수들을 선언했습니다. 또한 min함수를 struct에 대해 사용하기 위해 연산자 오버로딩(함수 중복정의) 을 사용했습니다. 수를 입력 받..
(C++) - 백준(BOJ) 14438번 : 수열과 쿼리 17 https://www.acmicpc.net/problem/14438 14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net segment tree문제였습니다. 📕 Code #include #define INF 0x3f3f3f3f #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n, q, num[100001], tree[..
(C++) - 백준(BOJ) 5676번 : 음주 코딩 https://www.acmicpc.net/problem/5676 5676번: 음주 코딩 각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다. www.acmicpc.net segent tree를 이용해 구간곱을 O(logN)만에 구하는 문제였습니다. 📕 풀이방법 n이 10^5고 모든 원소가 범위의 최대인 100이라면 100^(10^5)이므로 단순 정수 자료형들로는 해결할 수 없습니다. 다행히 출력해야하는 것이 부호 또는 0이기 때문에 적절히 치환해준다면 범위 초과를 넘길 수 있습니다. 📔 입력 및 초기화 1. n만큼 원소를 vector 변수 v에 입력 받습니다...
(C++) - 백준(BOJ) 11505번 : 구간 곱 구하기 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 기존 구간합을 구하는데 이용하는 segment tree를 약간 응용한 문제였습니다 📕 풀이방법 📔 입력 및 초기화 n까지 수들을 입력받습니다. 이후 각 구간곱들을 tree라는 long long형 배열에 저장합니다. 📔 풀이과정 1. a = 1일 때 : b-1이 가르키는 부분을 c로 갱신하며 구간곱들을 새로 바뀐 c에 맞춰 갱신 해줘야합..
(C++) - 백준(BOJ) 2268번 : 수들의 합 https://www.acmicpc.net/problem/2268 2268번: 수들의 합 첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 www.acmicpc.net 기본 segment tree였습니다. 풀이방법 1. 기본적으로 data n개에 대해 segment tree를 만드는데 필요한 공간은 n보다 크면서 가장 가까운 제곱수 * 2입니다. 제곱수를 찾기 귀찮기 때문에 n*4만큼의 공간을 할당해줍니다. 2. 입력에 대해 들어있는 값을 갱신하거나 또는 구간의 합을 출력합니다. 명령어가 1인경우에는 입력받은 i,j의 범위가 오름차순이 아..

티스토리툴바