본문 바로가기

알고리즘225

BOJ 14463 - 소가 길을 건너간 이유 9 (세그트리, 라인스위핑) https://www.acmicpc.net/problem/14463 distinct한 좌표를 갖는 교차하는 선분쌍의 '개수' nlogn에 구하기 참고: n^2에 모든 교차하는 선분쌍을 하나하나 들여다 보는 로직 https://suuntree.tistory.com/112 선분i를 처음부터 순차로 보면서, 선분 i의 범위가 [lo,hi]라면, hi를 세그먼트트리에서 1 올리는 update를 해준다. 그러면 0~i-1번 선분과 선분 i가 교차하는 쌍의 개수는 psum[i끝점] - psum[i시작점]이다. 다시말해서, 0~i-1번 선분 중에 선분 i[lo,hi]와 교차하는 선분의 개수는, 끝나는 점이 [lo,hi]에 속하는 선분의 개수이다. (선분i에 포함되는 선분은 i+1이후이므로 신경쓰지 않는다.) cons.. 2020. 2. 29.
BOJ 6549 - 히스토그램에서 가장 큰 사각형 (세그트리, 분할정복, monotonic stack) https://www.acmicpc.net/problem/6549 웰노운이지만 오늘에서야 이해한 문제. 참고: https://www.acmicpc.net/blog/view/12#comment-442 히스토그램이 주어진다. 구간 [s,e] 넓이는 rmq(s,e)*(e-s+1)일 때, 최대 사각형의 넓이를 구해라. rmq엔 구간 최소 높이를 갖는 '인덱스'를 저장한다. 구간 [s,e]에서 사각형의 최대 크기는 go(s,e) 1. 구간 최소 높이를 최대 높이로하는 사각형 h[rmq(s,e)]*(e-s+1) 2. 그 인덱스 좌측에서의 사각형 최대 크기 go(s,rmq(s,e)-1) 3. 그 인덱스 우측에서의 사각형 최대 크기 go(rmq(s,e)+1,e) go(s,e) = max(1,2,3)이다. 위 백준님의 .. 2020. 2. 29.
BOJ 2243 - 사탕 상자 (세그트리, k번째 수) https://www.acmicpc.net/problem/2243 기본문제. 사탕의 맛이 1~1e6으로 주어질 때, 최대 1e5개의 쿼리가 주어진다. 1 : k -> k번째로 맛있는 사탕의 맛 출력 2 : i d -> 맛i를 갖는 사탕의 수를 d만큼 변화 구간합 세그트리를 마련한다. 2번쿼리는 일반적인 세그트리 update와 같은 논리로 짜면 된다. 1번쿼리는 어떻게 짤까? 예를 들어 3번째 원소를 찾으려고 할때, 왼쪽 자식노드에 3이하가 들어있다면 왼쪽자식노드로, 3초과가 들어있다면 우측자식노드로 재귀를 진행하면 된다. // k번째 수 찾기 int kth(int node, int st, int en, const int k) { if (st == en) return st; int mid = (st + e.. 2020. 2. 29.
BOJ 11982 - Angry cow (그리디, 전처리dp, 투포인터) https://www.acmicpc.net/problem/11982 어렵다 공식홈페이지와 rdd6584님의 코드를 보며 공부했습니다. 일직선위에 최대 5e4개의 표적이 n개 주어진다. 폭발반경이 R인 폭탄을 일직선 위에 던지려고 한다. 표적은 터지면 이전 폭발반경보다 1 작은 만큼의 폭발반경을 가지며 연쇄폭발한다. 적절한 곳에 폭탄을 던진다면 모든 표적을 부수기 위해 필요한 폭탄의 최소 폭발반경은 몇일까? 소수점 첫 자리까지 나타내라 폭탄은 어떤 두 표적 정 가운데에 떨어지는 것이 최적이다. ->(x+y)/2로 표적의 위치를 특정할 것이므로 표적의 위치는 xxx.5 혹은 xxx.0이다. 모든 표적의 좌표를 두배로 하고 폭발반경이 2씩 줄어든다고 처리하면 정수연산만으로 풀 수 있다. 표적은 오름차순 정렬해.. 2020. 2. 27.

티스토리툴바