본문 바로가기

세그먼트 트리

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.. 더보기
BOJ)9345 디지털 비디오 디스크(DVDs) 문제:icpc.me/9345 번호 순서대로 있던 DVD를 쿼리에 따라서 바꿔줄 때 a번부터 b번까지 DVD를 가져왔을 때 a~b번까지 DVD가 모두 있나 확인하는 문제이다. a~b번까지 DVD가 모두 있나 확인할 수 있는 방법은 a~b까지의 최댓값과 최솟값을 구해주어 a와 b인지 확인해주는 작업을 해주면 된다. 이는 세그먼트 트리를 이용하여 구해줄 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include #define MAX_N 100000#define INF 987654321using namespace std;.. 더보기
BOJ)1321 군인 문제:icpc.me/1321 군인들이 번호 순서대로 각 부대에 배치되어 있을 때 i번째 군인이 몇번 부대에 배치되어 있는지 확인하는 문제이다. 이 때 부대별로 군인들의 수가 감원이 일어 날 경우 모든 군사들이 재배치를 받게 되므로 세그먼트 트리를 이용하여 갱신과 쿼리를 O(logN)시간에 해결 해 줘야 한다. 쿼리를 처리하는 방법은 노드에 구간 합을 저장하고 있을 때 내가 부대를 찾아야하는 군번을 가지고 왼쪽 자식 노드와 비교를 하여 왼쪽 자식 노드가 더 큰 값을 가지고 있을 경우 내가 찾고자 하는 부대는 왼쪽에 있는 것이므로 왼쪽 자식을 재귀 호출하고, 아닐 경우 오른쪽 자식을 재귀 호출 하는데 이 때 우리는 왼쪽 자식 수만큼을 제외하고 봐야 하므로 찾아야하는 군번에 왼쪽 자식의 수만큼 빼준 값으로 재.. 더보기

티스토리툴바