돌이 코딩하는 방

이번 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..

사실 Technique라고 하기도 뭐하지만... 최근에 여러문제들을 풀면서 느낀 점이 있어서 간단하게 적어 놓으려고 한다. Prefix Sum 이란? Prefix = 접미사 sum = 합. 그니까 앞에서 부터의 합을 의미한다. 어떠한 값이 들어있는 기존의 배열 arr이 존재한다고 하면 $pre[x]=\sum_{i=1}^{x} arr[i]$ 로 표현되는 값들이 prefix sum들이라는 것이다. How? prefix sum 배열을 채우는 것은 $O(N)$만에 정말 간단하게 할 수 있다. $pre[i]=pre[i-1]+arr[i]$ 로 할 수 있다. 어떤 식으로 활용해야 할지에 대해서 고민을 해봐야 한다. prefix sum은 구간 합을 구할 때 주로 사용되어진다. i부터 j까지의 구간합은 $pre[j]-p..

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

'Tree에서는 Centriod를 잡고 생각하면 편하고 그래프에서는 SCC를 잡고 생각하면 편하다.' 라는 말이 있다. 사실 수준급의 그래프 문제를 많이 풀어본 것이 아니라서 별로 공감은 안되지만, SCC가 정말 좋은 테크닉이라는 것은 인정하고, 저러한 말이 나올 정도로 굉장히 유용하게 쓰일 수 있다. 이번 포스팅은 그러한 SCC에 대해서 설명하려고 한다. SCC scc란 무엇일까? scc는 strongly connected component로 약자를 풀어내면 해석이 되는 다른 줄임말과 다르게 바로 알 수가 없다. 보통 방향그래프에서의 scc를 말하며, scc는 아래의 두가지 조건을 만족하는 서브 그래프이다. 1. 한 scc안에 속한 임의의 어떤 한 노드 A와 다른 한 임의의 노드 B에 대해서 A에서 B..

세그먼트 트리를 이용하여 구할 수 있는 다양한 값들을 소개하려고 한다. 그 중 이번 포스팅은 사람들에게는 Inversion counting이나 LIS등으로 더 친숙한 2-elements 문제나, 특정 문제에서 사용되어진 3-elements 문제에 대해서 말해보려고 한다. 2-elements는 하나의 객체가 2가지 요소 (두개의 값, 하나의 값과 입력순서 등) 를 가지고 있으며 그 두가지 요소가 모두 작은 객체의 갯수 (LIS) , 둘 다 작은 객체의 존재 여부, 둘의 우선 순서가 뒤바뀐 쌍의 수(inversion counting)등을 구하는 문제이다. 3-elements는 하나의 객체가 3가지 요소를 가지고 있으며 세가지 요소가 모두 작은 객체의 존재여부 등을 다루는 문제이다 (굉장한 학생) 2-Elem..

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

sqrt, 루트계의 스페셜리스트 알고리즘인 Mo's algorithm을 소개하려고 한다. 어떤 문제를 해결할 때 기본적으로 루트풀이는 친숙하지 않아서 떠올리기 힘들다. 하지만 그 와중에 Mo's algorithm은 굉장히 신박한 아이디어로 만든 시간복잡도이기 때문에 이 알고리즘은 정말 '알고 있어야' 사용이 가능하고 문제를 풀 수 있을 것이다. Mo's algorithm 이란? Mo's algorithm은 업데이트가 없이 오프라인으로 구간 쿼리가 많이 주어질 때, 그 구간쿼리들을 효율적으로 처리하는 알고리즘이다. 기본적으로 오프라인 쿼리여야 되고, 처리하는 쿼리들의 순서를 잘 조정함으로서 더 효율적으로 처리를 할 수 있게 됩니다. Mo's algorithm의 작동 방식 1. 어떤 쿼리 (구간) 에 대한 ..

LCA란? LCA는 Lowest Common Ancestor의 약자로 해석하면, 최소 공통 조상(가장 낮은 공통 조상)이라는 뜻을 가지고 있다. '조상'이기 때문에 트리에서 사용하며, 다양한 특징을 가지고 있어 트리 문제를 해결할때 기초로 잘 사용되어진다. 트리에서는 조상이 존재한다. 어떤 노드의 부모, 부모의 부모, 부모의 부모의 부모해서 루트까지의 모든 노드를 조상노드라고 하며, 공통 조상은 2개의 노드들에 대하여 어떤 노드가 그 두 노드의 공통적으로 조상일때를 말한다. 그러한 공통 조상들 중에서 가장 낮은 (깊이가 깊은, 처음 만나는) 공통조상이 최소 공통 조상 즉 LCA가 된다. 위와 같은 트리가 있다고 할 때 LCA(9,10)=4, LCA(9,11)=2, LCA(5,9)=2, LCA(12,13)..

도입 다음과 같은 문제를 푼다고 생각해보자. 자동차 경주대회가 있었다. 먼저들어온 순서대로 N대의 자동차들에 대한 평균 속력이 주어진다. 하지만 이 차들중에 평균속력이 K이상인 차들은 우승자격이 박탈된다. 어떤 차가 우승하게 될까? 파라메트릭 서치란? 파라메트릭 서치(Parametric Search)는 기본적으로 이분탐색을 베이스로 깔고 들어간다. 나는 Parametric Search를 "조건내 최대(최소)를 찾는 문제를 log의 시간복잡도를 사용해 결정문제로 바꾸는 테크닉"이라고 말하고 싶다. 이 말만 들어서는 의미를 제대로 파악하기 힘들고 도입의 문제를 이용해 이 말을 풀어나가보려고 한다. 파라메트릭 서치의 역할 도입의 문제를 보면 K미만의 숫자 중 가장 큰 숫자를 찾는 문제가 된다. 하지만 Para..

DP 문제에서 $O(N)$의 시간복잡도를 $O(lgN)$으로 줄여주는 또 다른 테크닉이다. DP에 DnC는 굉장히 안어울릴 것 같다. 사실 그렇긴 하다. 사용되어질 조건이 까다롭고, 이 문제에서 DnC를 사용할 수 있는 조건을 만족하는지 알기도 굉장히 어렵다. DnC Opmization을 사용하는 문제는 대체로 굉장히 까다롭고 어렵다. DnC Optimization이란? Divide and Couquer Optimization의 약자로 한글로 해석하면 분할정복 최적화 기법이다. 말 그대로 분할 정복을 사용해서 최적화를 시키는 기법이다. When? $DP[i]=\underset{1\leq j\leq N}{min}F(i,j)$ 에서 $DP[i]=F(i,j)$를 만족하는 $j$를$A[i]$라고 할 때, $If..