본문 바로가기

분류 전체보기

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#.. 더보기
BOJ)5419 북서풍 문제: icpc.me/5419 북서풍을 타고 항해할 수 있는 섬의 쌍의 개수를 구하는 문제이다. 여기서 북서풍을 타고 항해할 수 있는 섬이란 어떤 섬 기준으로 x좌표가 해당하는 섬보다 크거나 같고 y좌표가 해당하는 섬보다 작거나 같은 섬들을 말한다. 결국 우리는 각 섬마다 x좌표가 작으면서 y좌표는 큰 섬들의 개수를 구한 뒤 그 합을 출력하면 된다. 우리는 x좌표가 작은 수를 우선적으로 정렬하되 x좌표가 같을 경우 y좌표가 큰 수를 우선적으로 정렬을 할 것이다. 이렇게 정렬을 했을 시에 먼저 등장하는 좌표뒤에 나오는 좌표들 중 북서풍을 타고 항해할 수 있는 섬이 없다는 것은 자명하다. 따라서 우리는 정렬을 해준 뒤 순서대로 봐주면 된다. x좌표 기준으로 정렬을 했으므로 우리는 먼저 등장했던 섬들 중에서 .. 더보기
BOJ)1849 순열 문제: icpc.me/1849 (A[i]=i보다 큰 수들의 개수)일 때 원래 수열을 구하는 프로그램을 작성하면 된다. 작은 수 부터 채워 나간다고 할 때 A[1]이 5 라면 1은 수열의 6번째 수가 될 것이다. 우리는 수열을 세그먼트 트리를 이용하여 구해보자. 먼저 리프에 해당하는 모든 노드를 1로 채워준 후 구간합을 업데이트 시켜준다. 이후 a[i]를 확인 할 때 a[i]+1번째에 해당하는 노드를 찾아준 뒤 수열의 해당하는 자리에 i를 저장해 준다. 이후 노드 i를 0으로 초기화 시켜준다. 이런 방식으로 나보다 큰 수들중에서만 내가 몇번째 위치에 있는지 확인 하여 수열을 채워 나간다. 1234567891011121314151617181920212223242526272829303132333435#incl.. 더보기