본문 바로가기

분류 전체보기

BOJ)10999 구간 합 구하기2 문제: icpc.me/10999 구간에 대한 합을 출력하는 문제이다. 그런데 쿼리중에 구간에 대한 갱신 연산을 하는 쿼리가 있다. 우리는 세그먼트 트리를 통해 구간에 대한 갱신과 합쿼리를 빠르게 처리 할 수 있지만 구간에 대한 갱신을 세그먼트 트리로만 하려고 한다면 갱신의 경우 최악의 시간복잡도는 O(NlogN)이 될것이다. 만약 쿼리가 전부 갱신만 들어온다면 시간 복잡도는 O(N(M+K)logN)로 당연히 시간초과를 보게 될 것이다. 그래서 우리는 lazy propagation을 이용하여 구간에 대한 갱신을 조금 더 빠르게 해주는 테크닉을 이용하여 문제를 풀어야만 한다. lazy propagation에 대한 설명은 여기에 친절하게 되어있다. 1234567891011121314151617181920212.. 더보기
BOJ)11505 구간 곱 구하기 문제:icpc.me/11505 구간에 대한 곱을 출력하는 문제이다. 값의 갱신이 빈번하게 일어나기 때문에 세그먼트 트리를 이용해주면 된다. 곱셈의 특성상 구간의 곱을 가지고 있으면 무수히 커질 수 있기 때문에 문제에서 모듈러연산을 요구한다. 이때 단순히 답에만 모듈러연산을 해준다면 노드가 가지고 있는 값이 오버플로우 될 수 있으므로 우리는 노드가 가진 값들을 업데이트 할 때 와 쿼리를 처리할 때도 모듈러연산을 해줘야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MOD 1000000007#define MAX_N 1000000typedef long long .. 더보기
BOJ)5012 불만 정렬 문제: icpc.me/5012 iAk를 만족하는 경우의 수를 세는 문제이다. 우리는 j를 기준으로 생각해보자. 현재 j를 보고 있을 때 경우의 수에 해당할 수 있는 경우는 result = SUM [ (j보다 먼저 등장하고 Aj보다 큰 수) x (j보다 나중에 등장하고 Aj보다 작은 수) ] 으로 나타낼 수 있다. 따라서 우리는 쿼리를 다 받은 후 앞에서 부터 보면서 j보다 먼저 등장하면서 Aj보다 큰 수들을 먼저 기록 한 후 다시 한번 뒤에서부터 보면서 j보다 늦게 등장하면서 Aj보다 작은 수들을 기록해준 뒤 곱해주어 더한값을 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #in.. 더보기
BOJ)3002 아날로그 다이얼 문제: icpc.me/3002 N개의 다이얼이 주어졌을 때 구간이 주어지면 구간의 합을 구한뒤 구간의 수를 전부 1씩 증가시켜주는 문제이다. 얼핏보면 구간에 대한 증가연산과 구간합을 출력하면 되니 레이지 프라퍼게이션을 이용한 구간합으로 바로 해결할 수 있을것 같지만 문제는 다이얼이기 때문에 9를 증가시키면 0이 된다는 것이다. 결국 0~8의 숫자는 증가시킬 경우 1씩증가하게 되지만 9는 증가시킬 경우 오히려 -9가 되버린다. 이래서 구간에 대한 합을 한번에 노드에 저장하고 있을 경우 증가연산이 애매해질 우려가 있다. 따라서 우리는 구간마다 노드를 10개씩 만들어 0~9까지의 개수를 저장하여 값을 증가시키는 경우 0~9 ->(0+x)%10~(9+x)%10까지로 쉬프트 시킬것이다. 물론 구간에 대한 증가가 .. 더보기
BOJ)1168 조세퍼스 문제2 문제: icpc.me/1168 N명의 사람이 원을 이루며 앉아있고 M번째 사람을 제거하면서 진행할 때 제거되는 순서에 따른 순열을 출력하는 문제이다. 세그먼트 트리를 이용하여 현재 위치에서 M번째 사람을 찾아내서 풀면 된다. 이때 주의 할 점은 환형이기 때문에 남아있는 사람수를 고려하여 모듈러 연산이 필요하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include using namespace std;int seg[400040];int n, m;vector ans;int update(int pos, int val, int node, .. 더보기
BOJ)9426 중앙값 측정 문제: icpc.me/9426 n개의 수열이 있을 때 K의 연속 부분 수열의 중앙값의 합을 구하는 문제이다. 앞에서부터 K개의 수를 세그먼트 트리에 업데이트 시켜준 후 N까지 1개씩 지우고 업데이트 시켜주면서 중앙값을 구해주면 된다. 중앙값은 앞에서부터 (k+1)/2 수를 찾으면 된다. 1234567891011121314151617181920212223242526272829303132333435#include #include #define MAX_N 250001#define MAX 65536using namespace std;typedef long long ll;ll seg[4 * MAX_N], a[MAX_N], n, k, res;ll update(ll pos, ll val, ll node, ll x, .. 더보기
BOJ)5676 음주 코딩 문제: icpc.me/5676 값의 갱신이 일어날 때 i~j까지 모든 수를 곱했을 때 음수인지 양수인지 0인지 판단하는 프로그램을 작성하는 문제이다. 음수인지 양수인지 0인지만 판단하면 되므로 세그먼트 트리를 이용한 구간 곱으로 쉽게 구할 수 있다. 입력된 수가 양수일 경우 1 음수일 경우 -1 0일 경우 0으로 값을 갱신해주며 쿼리에 따른 값을 출력해 주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #define MAX_N 100000using namespace std;int seg[4 * MAX_N], n, k, a[MAX.. 더보기
BOJ)12016 라운드 로빈 스케줄러 문제: icpc.me/12016 0번 작업부터 N-1번 작업까지 순서대로 수행 할 때 스케줄러는 한 작업을 1초 실행 시킨 뒤 다음 작업으로 넘어간다고 한다. 이 때 각 작업들이 언제 완료 되는지 구하면 된다. 우리는 문제를 풀기위해 쿼리를 전부 받은 뒤 정렬하여 가장 짧은 작업부터 수행해보자. 한 작업을 끝냈을 때 다음작업은 이미 끝난 작업의 완료하는데 필요한 수행시간을 포함한다. 따라서 한 작업이 끝날 때 마다 이미 끝난 작업의 총 수행시간은 따로 더해서 저장할 필요가 있다. i번째 작업을 할 때 i번째 작업을 완료하는데 필요한 시간을 t라고 하면 답= (1~i번째 작업중 끝나지 않은 작업의 수)*t+(i+1~N번째 작업중 끝나지 않은 작업의 수)*(t-1) + (이미 끝난 작업의 총 수행시간) 이 .. 더보기
BOJ)3653 영화 수집 문제: icpc.me/3653 순서대로 쌓여있는 DVD가 있을 때 영화를 볼때마다 위에 몇개의 DVD가 쌓여있는지 출력하는 문제이다. 이 때 본 영화는 맨위에 쌓는다고 한다. 우리는 세그먼트 트리의 구간합을 통하여 문제를 해결할 수 있다. 우선 n+m+1개의 노드중 m+1~n+m+1에 해당하는 리프에 1씩 업데이트 시킨다. 이는 n개의 DVD가 m+1부터 순서대로 존재한다는 것을 의미한다. 이 때 i번 DVD는 i+m에 존재한다고 기록해 준 뒤 i번째 영화위의 DVD의 개수는 1~(i번 DVD의 위치-1)의 구간합으로 구해줄 수 있다. DVD를 뺐으므로 원래 DVD의 위치는 0으로 갱신해 준 후 맨 위에 DVD를 갱신해 줘야한다. 맨위는 i번째 쿼리를 처리할 때 m+1-i 번째 위치일 것이다. 해당 위치.. 더보기
BOJ)6549 히스토그램에서 가장 큰 직사각형 문제: icpc.me/6549 히스토그램에서 가장 큰 직사각형을 구하는 문제이다. 세그먼트 트리를 이용한 분할 정복을 이용하여 풀 수 있는데 i,j까지의 구간의 직사각형 넓이는 i,j까지의 높이가 최솟값인 부분에 의하여 결정된다. 따라서 우리는 높이가 최솟값인 부분을 기준으로 양쪽을 분할 정복해 나갈 것이다. 이를 계산하기 위하여 높이가 최솟값인 지점을 세그먼트 트리에 저장을 해줘야 한다. 전체에서 넓이를 구하여 높이가 최솟값인 지점을 기준으로 양쪽의 넓이를 다시 구해주면서 최종적으로 높이의 최댓값을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#.. 더보기

티스토리툴바