아무 말

IDEA Ternary search는 아래로 볼록인 함수에서 최솟값, 위로 볼록인 함수에서 최대값을 찾을 때 이용할 수 있다. 어떤 함수 \( f(\boldsymbol{\mathrm{x}}) \)가 있다고 하자. 이 함수는 \(\boldsymbol{\mathrm{x}}_i \) for all \(i\)에 대해서 아래로 볼록이다. 즉, fixed \(\boldsymbol{\mathrm{x}}_j\) for all \(j \neq i\) 이면, \(f(\boldsymbol{\mathrm{x}})\)는 아래로 볼록이다. 이때, 각 \(\boldsymbol{\mathrm{x}}_i\)에 대해서 ternary search를 이용해 optimization을 해주면, 함수는 조금씩 최적화 될 것이라는 생각을 할 수 ..

들어가며.. 그래프 이론에서의 가장 기본적인 부분으로, 많은 그래프 알고리즘에는 그래프 탐색이 이용된다. 본문에서는 BFS와 DFS에 대해 다룬다. 그래프 탐색의 시간복잡도 그래프 탐색은 말 그대로 그래프를 탐색하는 것이다. 모든 정점과 간선을 확인해야 한다. 따라서 어떤 방법으로 탐색을 하던 간에 알고리즘의 시간복잡도는 \(\Omega(|V+E|)\)이다. 그리고 본문에서 다루게될 DFS와 BFS는 인접 리스트를 이용할 때 \(\Theta(|V+E|)\)의 시간복잡도를 가진다. DFS DFS(depth first search, 깊이 우선 탐색)은 현재 방문할 수 있는 vertex 중에서 depth가 큰 vertex부터 방문하는 방법이다. 다만, 이는 검색 트리에서의 이야기이고 본문에서 다룰 그래프에서의..

INTRODUCTION Segment tree를 이용해서 수열에서의 구간 합을 구하는 방법은 매우 잘 알려져 있다. 본문에서는 수열의 값이 0 또는 1밖에 없을때 이를 더 빠르게 처리하는 방법에 대해서 다루고자 한다. IDEA 컴퓨터에서 bit의 수를 세는 것은 \(O(1)\)에 수행할 수 있다. 또한, 이 bit를 셀 때 세고싶은 구간만 나눌 수 있다. 간단히 원하는 구간만 1로 채워져 있는 bitset과 bitwise AND 연산을 이용하면 된다. 그렇다면 이것으로 구간 쿼리를 처리하는 방법에 대해 감이 어느정도 왔을 것이다. Segmet tree의 맨 아래쪽 리프를 모두 bitset으로 만든다. 그리고 나머지는 원래대로 처리하면서 리프의 bitset에서 값이 1인 bit의 수를 세서 위쪽 리프로 올..

바이토닉 투어란? 바이토닉 투어(Bitnoic Tour)또는 바이토닉 TSP(Bitonic Traveling Salesman Problem)는 외판원 문제의 일반화로, 유클리드 평면 위의 정점에서 이루어지며, 수직선과 투어를 표현한 다각형이 최대 2번 교차해야 한다는 조건이 붙어있다. 바이토닉 투어는 일반적인 외판원 문제와는 다르게, 다항 시간 내에 해결할 수 있는 방법이 존재한다. 그리고 이를 최적화 하면 \(O(N \log(N))\)에 문제를 해결할 수 있다. 외판원 문제와의 관계 당연하게도 유클리드 평면 위의 외판원 문제의 해와 바이토닉 투어의 해는 다르다. 하지만, 길게 늘어진 공간에서는 같을 수 있는데, 주어지는 모든 점의 좌표가 정수일 경우 이 늘어진 공간의 폭이 \(2 \sqrt{2}\)이하..

서론 팩토리얼의 역수의 합이 수렴함은 잘 알려진 사실입니다. 이항 계수의 역수의 합도 수렴할까요? 이항 계수의 역수의 성질 [1] $$ \begin{matrix} {n \choose k}^{-1} &=& \frac{k!(n-k)!}{n!} \\ &=& \frac{(n-1)!(n-k)!}{n!}(n-(n-k)) \\ &=& \frac{(k-1)!(n-k)!}{(n-1)!}-\frac{n-k}{n-k+1}\frac{(k-1)!(n-k+1)!}{n!} \end{matrix}$$ 따라서, $$ {n \choose k}^{-1}={n-1 \choose k-1}^{-1}-\frac{n-k}{n-k+1}{n \choose k-1}^{-1} $$ 이항 계수의 역수의 합 [1] 이제, \( I_{n}=\sum_{k=0}..

일단 이 글에서 이분 탐색이 무엇인지에 관한 설명은 하지 않겠습니다. 이미 잘 정리된 글이 많으며, 잠깐만 구글링을 해 보아도 쉽게 찾을 수 있습니다. (물론 CLRS를 봐도 좋고) 이 포스팅에서는 실수와 정수 범위에서 이분 탐색을 할 때의 탐색 범위에 관해 다룹니다. 1. 정수 이분 탐색 말 그대로 정수 범위에서의 이분 탐색이며, 특정한 조건을 만족하는 최초의 정수 같은 것을 찾을 때 이용합니다. 범위 설정 현재 탐색 범위가 \(\left [l, r\right]\)이고, \(m=\lfloor \frac{l+r}{2} \rfloor\)라고 합시다. 그리고 \(g(m)\)이 우리가 만족하길 바라는 조건입니다. 이때 범위를 나눈다면 두 가지 경우가 있습니다. 1. \(g(m)\)이 True이면, 모든 \(n..

INTRODUCTION 이번 포스팅에서는 최대 연속 부분합을 다루는 세그먼트 트리에 대해 다루고자 한다. 이 기술은 대한민국에서 특히 더 잘 알려져 있다. 2014년 한국정보올림피아드 중등부 4번 문제 금광을 통해 유명해졌으며 이로 인해 주로 "금광 세그"라는 이름으로 불린다. 해당 세그먼트 트리에 관해서는 Codeforces에서 찾을 수 있는 ITMO Academy: pilot course에서도 다루었다. 강의가 필요하다면 확인하기 바란다. https://codeforces.com/edu/course/2/lesson/4/2 Courses - Codeforces codeforces.com IDEA 우리가 segment tree를 이용할 때를 생각해 보자. tree의 노드가 관리하는 segment를 다른 ..

https://www.acmicpc.net/problem/1615 1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net 들어가며.. 기존에 이 문제의 풀이는 \(O(M \log(N)) \)에 작동하는 세그먼트 트리를 활용하는 것으로 알려져 있었다. 하지만, 이번 포스팅에서는 조금 다른 풀이를 다루고자 한다. 풀이 무려 \(O(NM)\)에 작동하는 코드가 통과된다. 먼저, 간선이 연결된 정점 중, A에 속한 정점을 기준으로 단조 증가하게 정렬한다. (만약 그 정점이 같은 것 들은 B에 속한 정점을 기준으로..

들어가며.. 이전에 Heavy-Light Decomposition에 대해 다룬 적이 있다. 이는 트리를 몇개의 선형 배열로 바꾸는 것이며, 주로 특정한 두 정점을 잇는 경로에 포함되는 간선의 가중치나 정점에 관한 쿼리를 처리하는 데에 이용된다. 그렇다면, 해당 노드와 그 노드의 모든 자식 노드들에 관한 쿼리는 어떻게 처리할까? Euler tour technique 오일러 투어 테크닉(Euler tour technique)은 Tarjan과 Vishkin이 제안한 방법이다. 이 방법을 오일러 투어 테크닉이라고 부르는 이유는 검색 트리에서 이 테크닉을 통해 정점에 numbering 한 후, 각 간선의 역방향 간선을 만들어(자식 → 부모) numbering 한 순서대로 나열하면, 오일러 회로로 나타내지기 때문이..