[BOJ 2912]백설공주와 난쟁이 - P3 문제 설명 난쟁이가 n명 주어진다. 난쟁이는 각자 하나의 숫자를 갖고 있다. 이어서 쿼리가 주어진다. 각 쿼리는 [l,r]형태로 주어지는데, [l,r] 구간 안에서 난쟁이가 갖고 있는 특정 숫자의 개수가 구간의 길이(r-l+1)의 절반을 초과하는지 묻고 있다. 문제 풀이 특정 숫자의 개수가 구간 길이의 절반을 초과한다면, '반드시' 구간의 절반 경계를 지날 때, 등장하는 수가 같아야만 한다. 단, 역은 성립하지 않는다. 즉 절반의 경계에서 등장하는 수가 같더라도 그 수의 개수가 절반을 초과하지 않을 수도 있다. 따라서 그냥 정답의 '후보'만 된다는 것이고 이는 나중에 실제로 정답인지 검증하는 과정을 거쳐야 한다. 이러한 '후..
[BOJ 11658]구간 합 구하기3 - P5 문제 설명 2차원 grid에서 LeftTop의 좌표 ~ RightBottom의 좌표 사이에 있는 직사각형 형태 안에 포함된 숫자들 모두 더해서 값을 구하거나, 업데이트를 하는 쿼리를 수행한다. 문제 풀이 2차원 세그먼트 트리를 만든다. 기존 세그먼트 트리(1차원) 각각의 노드마다 또다른 세그먼트 트리를 매다는 형태이다. 가로(좌우)형태의 세그 트리를 main으로 짜고 곁가지로 세로(상하)형태의 트리가 달려있다고 생각하면 편하다. 소스 코드 #include #include #include typedef long long ll; using namespace std; const int SIZE = 1030; int tree[SIZE*4][SIZE*4]; int a..
[BOJ 2243] 사탕상자 - P5 문제 설명 1부터 100000까지 라벨이 붙은 사탕이 있다(초기에는 아무 사탕도 없는 상태). 두 가지 쿼리가 들어오는데 첫 번째 쿼리는 k번째로 작은 라벨이 몇 번인지 찾는 것(출력)이고 두 번째 쿼리는 'k번'사탕을 m개 추가하는 것이다. 풀이 [1,1000000]숫자 그대로를 세그먼트 트리의 인덱스로 사용할 것이다. k번째로 작은 라벨이 몇 번인지 찾기 위해서 트리의 i번째 노드는 i번 사탕이 총 몇 개 있는지를 저장하고 있다. 그래서 root 노드에는 결국 전체 사탕의 개수가 담기게 된다. 이제 쿼리에서 루트->리프로 내려갈 때 left child로 내려가면 [1,tree[left]만큼 작은 수가 저장되어 있다는 뜻이다. 따라서 k가 tree[left]보다 크..
[BOJ 1517] 버블 소트 - P5 문제 설명 : n개의 수를 버블 소트할 때, swap이 총 몇 번 일어나는지 세야 한다. 문제 풀이 : i번 째 수를 기준으로 자신의 왼쪽 ( [1, i-1] ) 에 있는 수들 중에서 자신보다 큰 값이 몇 개인지 세면 된다. n이 50만이기 때문에 log 시간만에 세야 한다. 두 가지 풀이가 가능하다. 첫 번째 풀이는 mergesort tree를 이용하면 된다. mergesort tree는 [l,r]구간 상에서 x보다 작은 수의 값을 log만에 구할 수 있다. 이는 얼마 전의 k번째 수 문제에서도 언급했었다. 두 번째 풀이는 바로 offline query를 이용하는 것이다. 이 문제는 쿼리별로 독립시행이다. 즉 이번 쿼리의 정답이 그 이후의 쿼리의 정답에 영향을 끼..
[CF 1042D] Petya and Array - 1800 문제 설명 : 배열 a[1], a[2].. a[n]이 주어져 있다. 여기서 임의의 [l, r] pair를 골랐을 때 $a[l]+a[l+1]+...a[r] < t$ 을 만족하는 pair가 총 몇 쌍인지 세야한다. 문제 풀이 : $a[l]+a[l+1]+..a[r] < t$ 식을 [1,n]까지의 누적합을 저장하는 누적합배열 $psum[]$ 배열을 활용하여 $psum[r] - psum[l-1] < t$ 로 변형할 수 있다. 그럼 결국에는 $psum[r] - t < psum[l-1]$을 구하는 문제랑 똑같아진다. 변수가 l, r 총 2개이기 때문에 l 이나 r 을 고정시켜놓고 나머지 다른 값만 log만에 구하면 된다. 나는 r을 고정시켜놓고 이를 만족시..
[BOJ 7469] K번째 수 - P3 문제 설명 : 문제 풀이 : mergesort tree를 이용해서 풀 수 있다. megesort tree는 트리의 노드가 값 하나가 아니라, 원소 그 자체를 담고 있기 때문에 여러개의 원소를 담고 있을 수 있다. 마치 merge sort가 되는 과정을 tree화 시킨 것이라고 보면 된다. 그래서 이분탐색으로 mid값을 지정하여 [l,r]구간에 mid 이하의 값이 몇 개인지를 log 만에 찾을 수 있다. 배울 점 : mergesort Tree를 이용하면 N개의 원소 중에서 [l,r]구간의 x보다 크거나 작은 원소의 개수를 log만에 구할 수 있다. #include #include #include using namespace std; const int SIZE = 10..
[BOJ 1725] 히스토그램 - P5 문제 요약 히스토그램에서 만들 수 있는 직사각형 중에서 가장 큰 넓이를 찾는 문제이다. 문제 풀이 직사각형의 넓이는 (r - l + 1) * getMin(l,r) 로 구할 수 있다. 여기서 문제는 N = 10만이므로 l,r을 전탐색으로 돌리면 시간이 초과하게 된다. 해결 방법은 세그먼트 트리에 가장 작은 값의 인덱스를 저장해놓는 것이다. 그래서 퀵소트가 작동하는 방식처럼 매 [l,r]구간에서 가장 작은 값의 인덱스를 찾아서 넓이를 구한 다음, 그 인덱스를 기준으로 좌, 우를 갈라서 똑같이 재귀적으로 넓이를 구해주면 된다. #include using namespace std; typedef long long ll; const int SIZE = 100009; cons..