돌이 코딩하는 방

이번에 소개할 Segment Tree 심화는 HLD이다. 원래는 Euler Tour 이후에 바로 글을 작성했어야 하는데, 대회 준비등의 이유로 다른 내용 관련 글을 계속 쓰다 보니까 계속 미뤄져서 이제서야 글을 쓰게 되었다. 사전 지식 (먼저 읽고 와야하는 글) stonejjun.tistory.com/103 세그 먼트 트리 - euler tour tree 설명글 What is HLD? 그러면 본격적으로 HLD는 무엇일까? HLD는 일단 Heavy - Light Decomposition의 약자이다. 무거운거 - 가벼운거 분해. 즉 Decomposition인데 Heavy Groupr과 Light Group으로 분리한다는 것이다. 그러면 여기서 좀 세부적으로 알아야 할 사항이 생긴다. 1. 뭐를 분리하는 것인..

이번 Segment Tree 심화는 Euler Tour Tree이다. 난 DFS Ordering Tree라는 이름으로 먼저 접했고, 이쪽이 좀 더 내용을 설명하기에 적합하다고 생각하지만 DFS Ordering Tree라는 이름은 사용을 거의 안하는 것 같다. 그래도 난 일단 DFS Ordering Tree라는 이름을 기반으로 설명을 하려고 한다. 사전 지식 Segment Tree, DFS DFS Ordering Tree 이 테크닉의 전체적인 요점은 트리를 일자로 편다는 것이다. 특히 트리를 일자로 펴서 리프로 만들어 버리고 그 리프들을 이용해 새로 세그먼트 트리를 만드는 것이다. 이때 트리를 일자로 펴는 방식은 이름 그대로 DFS Ordering을 통한 방식을 사용한다. When? 우리는 DFS Orde..

문제 태그 : https://www.acmicpc.net/problem/4002 문제 태그 더보기 Segment Tree 문제 소개 문제를 이해하기가 굉장히 어려웠다. 간단하게 설명을 하자면 트리에서 임의의 노드 x를 고른다. 그 후 x의 서브트리에서 몇 개의 노드를 고른다. 이때 노드의 비용의 합이 m이하가 되게 골라야 한다. 이때 고른 노드의 갯수와 x의 가중치의 곱의 최댓값을 구하는 문제이다. 문제 풀이 관찰 1. x가 정해진 상황에서 x의 서브트리에서 어떤 노드들을 골라야 할 때 결국은 갯수만 중요하기 때문에 당연하게도 비용이 낮은 것부터 선택을 해야한다. 즉 greedy 하게 고를 수 있다는 것이다. 이를 바꿔서 생각하면 비용이 많은 것부터 사용하지 않을 것이다. 관찰 2. 이를 트리의 노드 사..

문제 링크 : https://www.acmicpc.net/problem/14870 문제 태그 DP, Two pointer, Segment Tree 문제 풀이 일단 기존 상태의 상황을 구하는 것은 매우 쉬울 것이다. 당연히 DP로 구할 수 있고, 이때의 식은 다음과 같다. $DP[i][j]=max(DP[i-1][j],DP[i][j-1])+arr[i][j]$ 여기서 특정위치의 arr값을 1을 올리거나 내리는 값을 했을 때 DP 테이블이 어떤식으로 바뀌는지 구해야 하는 문제이다. 만약 $DP[i-1][j]$와 $DP[i][j-1]$이 둘 다 바뀌었으면 $DP[i][j]$도 바뀌었을 것이다. 혹은 둘 중에 더 큰 값, 즉 영향을 받는 값이 바뀌면 바뀔 것이다. 여기서 한가지 관찰을 해야한다. 한 가로줄에 대해서..

이번에 포스팅할 Segment Tree의 활용법은 구간 내에서 최대 부분합을 찾는 방법이다. 흔히 "금광 세그"라고 불리는 방식이며, 금광이라는 문제에 이 기법이 사용되어졌다. 어떠한 문제에서 두가지 쿼리가 주어졌다고 하자. 1번 쿼리로 수열에서 a번째 숫자를 b로 바꾸는 쿼리가 들어온다. 2번 쿼리로 l,r이 주어졌을때 수열의 [l,r]내에서 연속된 부분합의 최댓값을 구하는 것이다. 이러한 문제를 Segment Tree를 활용해서 해결할 것이다. 어떤 노드에 그냥 최대 부분합만 담고 있다고 생각해보자. 아래 두 개의 노드를 합칠때 그냥 둘 중 최댓값을 고르게 되면 왼쪽 절반 안에 속해있는 부분합과 오른쪽 절반안에 속해있는 부분합 밖에 알 수 없다. 두 구간을 걸친 부분들의 합은 고려해 줄 수 없는 것이..

Segment Tree의 활용성은 무궁무진하다. 정말 중요한 자료구조(알고리즘)이며, 대회에도 다양한 형태로 정말 많이 출제가 되어진다. 우리는 거의 모두 Segment Tree를 처음 배우는 과정에서 배열의 값이 바뀌어도 구간합을 빠르게 구할 수 있는 자료구조로서 Segment Tree를 배우지만, 이를 어떻게 추가적으로 활용하느냐, 노드에 어떤 다양한 값을 담느냐에 따라서 정말 다양한 연산을 처리할 수 있다. Segment Tree는 어떨 때 사용할까? 우리가 풀이에 세그먼트 트리를 고려해 볼 수 있는 상황은 간단하게 생각하면 두가지 정도 있다. 첫번째로 쿼리 형식으로 문제가 주어졌을 때이고, 두번째로 시간복잡도를 log로 만들고 싶을 때이다. log가 나오게 된다면 어떤 문제이던지 간에 한번쯤은 생..

문제 링크 : https://www.acmicpc.net/problem/13554 문제 태그 (관련 지식) 더보기 Mo's algorithm, Segment tree 문제 소개 길이가 N인 두 수열 A1, A2, ..., AN과 B1, B2, ..., BN가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: i ≤ p, q ≤ j이면서 Ap × Bq ≤ k 인 (p, q) 쌍의 개수를 출력한다. 문제 풀이 일단 오프라인 쿼리고 시간제한이 6초이다. 사실 어떻게 접근을 해야할지 모르겠다. 이 문제를 볼 때 쯤이면 다른 수열과 쿼리 문제를 꽤나 풀어봤을 것이고, 그러면 수쿼를 풀 수 있는 도구중 Mo's Algorithm이 생각이 날 수 밖에 없다. 하지만 문제가 있다. Mo's a..

문제 링크 https://www.acmicpc.net/problem/2243 문제 소개 두가지 행동을 하는 문제이다. 1. x 맛의 사탕의 갯수를 k개 변화시킨다. 2. k번째로 맛있는 사탕의 맛 수치를 출력한다. (1이 가장 맛있고 1000000이 최악) 문제 풀이 1번 쿼리는 굉장히 자주 나오는 쿼리이고 하나도 까다롭지 않게 작용한다. 중요한 것은 2번쿼리로 그니까 1부터 순서대로 늘어놓았을 때 k번째 숫자를 구하고 싶은 것이다. 구간 합 구하기의 가장 간단한 세그를 생각해보면 우리가 얻은 수 있는 값은 구간 의 합이다. 이 문제는 세그에는 추가적인 옵션을 가하지 않고, 이 값을 이용하여 문제를 해결할 수 있다. 이분 탐색이다. 1~i 구간의 합을 구할 수 있다. 그 값이 k이하인지 초과인지에 따라서..

관련 알고리즘과 함께 푼 수열과 쿼리 문제들을 쭉 포스팅 하려고 한다. 문제 링크 : https://www.acmicpc.net/problem/17408 문제 소개 1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ $10^9$) 2 l r: l ≤ i b.ff) { return tree[nod]=a; } else return tree[nod]=b; } pll sol(ll l ,ll r, ll s,ll e,ll nod) { if(er) return {0,0}; if(l

문제 태그: https://www.acmicpc.net/problem/7578 문제 소개 2열에 걸쳐 N개의 숫자가 주어진다. 윗줄과 아랫줄에 한쌍의 같은 숫자가 선으로 연결되어있다. 교차되는 선의 쌍의 수를 구하시오. 문제 풀이 일단 같은 숫자끼리 (a,b)의 쌍을 만들어서 생각해보자. 우리는 N개의 (a,b)를 얻을 수 있으며 그중에 i,j 에 대해 $a_{i} b_{j} $ 또는 $a_{i} > b_{i}, a_{j} < b_{j} $를 만족하는 쌍의 갯수를 구하면 된다. 한 쌍의 두 값에 대해서 순서가 바뀌어있는 갯수를 세는 문제이며, 이를 흔히 inversion counting 문제라고 불린다. inversion counting 문제는 merge sort 혹은 se..