1주차 주제는 segment tree / gridy / dynamic Algorithm
이렇게 8개가 숙제다
다들 코테 준비하던 분들이라서 왕창 잘해서 모든 알고리즘을 설명해주시진 않는다.
segment tree 만 설명해주시고, 나머지는 알아서 공부해야되는데 알고리즘 입문 단계인 나에게 좀 버겁다.
하지만 스터디장님이 설명을 끝장나게 잘해주심 외쳐 갓상규~!~!~!~!✨👍🎉
11/14(금)
segment tree
설명을 들을 땐 다 이해가 되고 모든 문제를 다 풀 수 있을 거 같은 기분이지만, 막상 문제는 안풀린다.
심지어 한 문제는 어제 5시간 고민하고, 다른 분 풀이도 참고하고 , 문제검색도 했는데 14번 도전했는데 아직까지 실패,,,
그래서 스터디장님 설명을 다시 되새기며 백준블로그에 segment tree 설명글 보면서 공부했다.
www.acmicpc.net/blog/view/9 백준도 블로그 있는 거 처음 알았음
백준 11659번 구간 합 구하기4 (www.acmicpc.net/problem/11659)
이거 하나 마저 못해서 우울해하고 있었는데 천사 조원분이 오류 잡아주심 히히
스터디장님이 계속 누적해서 더한 값을 배열에 넣으라 그래서 오호 하고 했는데 알고보니 이게
prefix sum 누적합 이란다.
#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
vector <int> arr;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
scanf("%d %d",&n,&m);
arr.resize(n);
scanf("%d",&arr[0]);
for (int i = 1; i < n; i++) {
int temp;
scanf("%d",&temp);
arr[i] = arr[i - 1] + temp;
}
for (int j = 0; j < m; j++) {
int a, b;
scanf("%d %d" , &a, &b);
if (a == 1) {
printf("%d\n" , arr[b-1]);
}
else {
printf("%d\n" , arr[b-1] - arr[a - 2]) ;
}
}
}세그멘트 트리를 이용해서도 풀어보았다.
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
vector <int> arr;
vector <int> segtree;
///초기화
int init(int start , int end , int idx ) {
if (start == end) return segtree[idx] = arr[start];
int mid = (start + end) / 2;
return segtree[idx] =( init(start, mid, 2 * idx) + init(mid + 1, end, 2 * idx + 1));
}
int query(int start, int end, int left, int right, int idx ) {
if (start > right || end < left) return 0;
if (left <= start && right >= end) return segtree[idx];
int mid = (start + end) / 2;
return (query(start, mid, left, right, 2 * idx) + query(mid + 1, end, left, right,2*idx+1));
}
int main() {
int n, m ;
scanf("%d %d", &n, &m );
//배열 초기화 resize
arr.resize(n);
segtree.resize(4 * n);
//배열 n개 입력 //arr[0] ~ arrr[n-1]
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
//초기화
init(0,n-1,1);
//m번 동안 구간의 최대,최소 출력
for (int i = 0; i < m; i++) {
int a , b;
scanf("%d %d", &a , &b);
printf("%d\n", query(0, n - 1, a - 1, b - 1, 1));
}
}
백준 2042번 구간 합 구하기 (www.acmicpc.net/problem/2042)
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
vector <long long> arr;
vector <long long> segtree1;
long long init(int start, int end, int idx) {
if (start == end) {
return segtree1[idx] = arr[start];
}
int mid = (start + end) / 2;
return segtree1[idx] = init(start, mid, 2 * idx) + init(mid + 1, end, idx * 2 + 1);
}
void change(int start, int end, int idx, int arr_idx, int new_num) {
if (arr_idx < start || end < arr_idx) return;
if (start == end) {
segtree1[idx] = new_num;
return;
}
int mid = (start + end) / 2;
change(start, mid, 2 * idx, arr_idx, new_num);
change(mid + 1, end, 2 * idx + 1, arr_idx, new_num);
segtree1[idx] = segtree1[idx * 2] + segtree1[idx * 2 + 1];
}
long long query(int left, int right, int start, int end, int idx) {
if (start > right || left > end) return 0; // 범위 밖인 경우
if (start >= left && end <= right) return segtree1[idx];
int mid = (start + end) / 2;
return query(left, right, start, mid, idx * 2) + query(left, right, mid + 1, end, idx * 2 + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
arr.resize(n);
segtree1.resize(4 * n);
for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);
init(0, n - 1, 1);
int a, b, c;
for (int j = 0; j < m + k; j++) {
scanf("%d %d %d", &a, &b, &c);
if (a == 1) {
change(0, n - 1, 1, b - 1, c);
}
else {
printf("%lld\n", query(b - 1, c - 1, 0, n - 1, 1));
}
}
}16번만에 성공함 히ㅎ,,, 장하다 나 자신
백준 11505 구간 곱 구하기 (www.acmicpc.net/problem/11505)
#include<iostream>
#include<stdio.h>
#include<vector>
# define N 1000000007
using namespace std;
vector <long long> arr;
vector <long long> segtree;
///초기화
long long init(int start , int end , int idx ) {
if (start == end) return segtree[idx] = arr[start] % N;
int mid = (start + end) / 2;
return segtree[idx] =( init(start, mid, 2 * idx) * init(mid + 1, end, 2 * idx + 1))% N;
}
long long query(int start, int end, int left, int right, int idx ) {
if (start > right || end < left) return 1;
if (left <= start && right >= end) return segtree[idx];
int mid = (start + end) / 2;
return (query(start, mid, left, right, 2 * idx) * query(mid + 1, end, left, right,2*idx+1))%N;
}
void change(int start, int end, int idx, int arr_idx, long long new_val) {
if (start > arr_idx || end < arr_idx) return;
if (start == end) { segtree[idx] = new_val; return; }
int mid = (start + end) / 2;
change(start, mid, 2 * idx , arr_idx, new_val);
change(mid + 1, end, 2 * idx + 1 , arr_idx, new_val);
segtree[idx] = segtree[idx * 2] * segtree[idx * 2 + 1];
}
int main() {
int n, m ,k;
scanf("%d %d %d", &n, &m ,&k);
//배열 초기화 resize
arr.resize(n);
segtree.resize(4 * n);
//배열 n개 입력 //arr[0] ~ arrr[n-1]
for (int i = 0; i < n; i++) {
scanf("%lld", &arr[i]);
}
//초기화
init(0,n-1,1);
//m번 동안 구간의 최대,최소 출력
for (int i = 0; i < m+k; i++) {
int a;
scanf("%d", &a);
if (a == 1) {
int b;
long long c;
scanf("%d %lld", &b, &c);
change(0, n - 1, 1, b - 1, c);
}
else {
int b, c;
scanf("%d %d", &b, &c);
printf("%lld\n", query(0, n - 1, b - 1, c - 1, 1));
}
}
}return 1 생각하고 혼자 뿌듯해하고있었는데 , 맨 마지막 printf를 찍을때만 query에 %1000000007 을 해주었는데 ,
segtree라는 배열에 값이 들어갈때부터 , 나머지 값이 들어가야 숫자가 작아진다는 질문 검색 보고 시무룩해짐 ㅜ
백준 23575 최솟값과 최댓값(www.acmicpc.net/problem/2357)
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
vector <long long> arr;
vector <long long> maxsegtree;
vector <long long> minsegtree;
//type =0 : max , type = 1 :min
long long init(int start , int end , int idx , int type) {
if (type == 0) {
if (start == end) return maxsegtree[idx] = arr[start];
int mid = (start + end) / 2;
return maxsegtree[idx] = max(init(start, mid, 2 * idx, type), init(mid + 1, end, 2 * idx + 1, type));
}
else {
if (start == end) return minsegtree[idx] = arr[start];
int mid = (start + end) / 2;
return minsegtree[idx] = min(init(start, mid, 2 * idx, type), init(mid + 1, end, 2 * idx + 1, type));
}
}
long long query(int start, int end, int left, int right, int idx , int type) {
if (type == 0) { // max 일 때
if (start > right || end < left) return 0;
if (left <= start && right >= end) return maxsegtree[idx];
int mid = (start + end) / 2;
return max(query(start, mid, left, right, 2 * idx, type), query(mid + 1, end, left, right,2*idx+1, type));
}
else { // min 일 때
if (start > right || end < left) return 1000000000;
if (left <= start && right >= end) return minsegtree[idx];
int mid = (start + end) / 2;
return min(query(start, mid, left, right, 2 * idx, type), query(mid + 1, end, left, right, 2 * idx + 1, type));
}
}
int main() {
int n, m;
scanf("%d %d", &n, &m);
//배열 초기화 resize
arr.resize(n);
maxsegtree.resize(4 * n);
minsegtree.resize(4 * n);
//배열 n개 입력
for (int i = 0; i < n; i++) {
scanf("%lld", &arr[i]);
}
//초기화
init(0,n-1,1,0);
init(0, n - 1, 1, 1);
//m번 동안 구간의 최대,최소 출력
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d %d", &a, &b);
long long max = query(0, n - 1, a-1, b-1, 1, 0);
long long min = query(0, n - 1, a-1, b-1, 1, 1);
printf("%lld %lld\n", min, max);
}
}쿼리에서 특정 조건을 처리하는 부분 짜는 게 제일 어려운 거 같다 아닌가 모르겠다 지금 나한텐 그렇다.
주어진 숫자가 0~1000000000이라서
max를 구할 때는 조건 밖의 숫자들은 모두 0으로 , min을 구할 때는 1000000000으로 처리해줬다.
'알고리즘 > 자료구조 & 알고리즘 개념정리' 카테고리의 다른 글
| c++ 알고리즘 스터디 2주차 - 크루스칼 알고리즘 (0) | 2020.11.26 |
|---|---|
| c++ 알고리즘 스터디 2주차 - 유니온파인드 (0) | 2020.11.26 |
| 알고리즘 스터디 1주차 - 투 포인터 (two pointer) (0) | 2020.11.15 |
| 알고리즘스터디 1주차 - dynamic programming (0) | 2020.11.15 |
| 알고리즘 스터디 1주차 그리디 알고리즘 (0) | 2020.11.14 |