아무 말

1. Introduction  Delaunay triangulation을 위한 알고리즘 중 가장 쉽고 간단한 것이 Bowyer-Watsom algorithm이다. Bowyer-Watson algorithm은 3차원 이상의 점들에 대해서도 Delaunay triangulation 계산할 수 있다는 장점이 있다. 또, Bowyer-Watson algorithm이 online query를 이용하는 알고리즘이라는 점에서 다른 알고리즘과 차별화된다. 이번 글에서는 이 Bowyer-Watson algorithm에 대해 설명하고 필자의 구현체에 대한 소개할 것이다. 2. Algorithm  Delaunay triangulation은 모든 삼각형의 외접원 내에 어떠한 점도 속하지 않도록 삼각형을 형성하는 것이다. 이는..

1. Introduction TSP나 할당문제 등 몇몇 최적화 문제에는 그 문제의 정확한 해를 찾거나 근사하기 위한 효율적인 알고리즘이 알려져 있다. 하지만, 그렇지 않은 경우도 존재한다. 이런 최적화 문제들의 해를 찾는 데에는 보통 EXP time이 소요되며, 근사하는 방법도 딱히 알려져 있지 않다. 그래도 널리 알려진 최적화 방법을 이용하면 값을 충분히 좋은 근사 해를 얻을 수 있다. 이런 방법에는 gradient descent, simulated annealing 그리고 genetic algorithm 등이 있다. 이중 simulated annealing과 genetic algorithm은 randomized search로 분류할 수 있다. 본문에서는 randomized search에 관해 다루고자..

서론  きたまさ法은 일본의 경기 프로그래머 wata가 블로그에서 소개한 점화식을 빠르게 계산하는 방법이다. 사실상 companion matrix의 멱승을 구하는 방법과 같지만, 선형 점화식이라는 특성을 활용하여 FFT를 이용, 선형 점화식의 항을 약간 더 빠르게 계산할 수 있다. ( \( O(k^2 \log N) \)에서 \( O(k \log k \log N )\). 따라서 \(k\)가 작은 점화식의 경우 별 의미가 없다. ) 이 테크닉의 이름은 블로그에서 소개한 wata가 붙였는데 きたまさ가 이 방법을 강력하게 주장했다고 한다. 이 きたまさ라는 사람이 한국에서는 잘 알려져 있지 않지만, kitamasa란 핸들을 이용하는 北川宜稔라는 사람으로, 일본에서는 '개미책'이라고 불리는 「プログラミングコンテストチ..

1. Introduction Ctrl + F 를 통해 인터넷에서 특정 문자열을 검색할 수 있다. 이런 종류의 검색에 이용되는 문자열 매칭 알고리즘 중 가장 유명한 것이 Knuth-Morris-Pratt(KMP) algorithm이다. 1.1. Navie Method KMP algorithm에 대한 설명을 하기 전 Naive한 문자열 매칭에 관한 이야기를 하겠다. 검색어, 즉 찾고자 하는 문자열을 \(P\)라 하자. 보통 이 \(P\)를 패턴이라고 한다. 우리는 \(P\)를 text \(T\)에서 몇 번 등장하는지, 어디서 등장하는지 알아야 한다. Naive하게 \(P\)를 \(T\)에서 찾으려면 아래의 과정을 수행하게 될 것이다. Naive-String-Matcher(\(T\),\(P\)) 1 \(n =..

본문의 내용은 E. W. Dijkstra의 A Note on Two Problems in Connexion with Graphs[1]에 관한 간단한 리뷰이다. Introduction Dijkstra's algorithm은 non-negative weighted graph에서 shortest path를 찾는 well-known algorithm이다. 현재 우리에게는 교과서[2]나, 알고리즘 문제해결과 관련된 서적에 적힌 버전이 널리 알려져 있다. 이번 글에서는 Dijkstra's algorithm의 초기 버전과 주로 Prim's algorithm[3]이라 불리는 minimum spanning tree(MST)를 찾는 알고리즘에 대해서 다루고자 한다. Minimum Spanning Tree[1] MST를 찾..

INTRODUCTION Model tree는 종속 변수의 몇 개의 독립된 구간으로 나누어 각각 다른 model을 적용하는 방법이다. 이번 글에서는 하나의 종속 변수와 독립 변수간의 회귀를 위한 model tree를 형성하는 방법에 대해 다루고자 한다. Model tree는 비선형 상관 관계를 선형 model을 통해 회귀할 수 있다는 점에서 일반적인 선형 회귀를 이용하는 것보다 좋다. 하지만, tree에 node가 너무 많아지면, 과적합이 발생할 수 있다. 본문에서는 이를 해결하기 위한 방법을 설명하려 한다. IDEA 먼저, model tree를 형성하기 위해 독립 변수를 몇 개의 구간으로 나누어야 한다. 이때, 간단히 같은 간격의 정확히 \(n\)개의 구간으로 나누겠다. 이 구간 마다 각각의 model을..

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의 수를 세서 위쪽 리프로 올..

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