아무 말

Knight's Tour  Knight's tour(기사의 여행)은 체스보드에서 나이트가 체스보드의 모든 칸을 방문하는 경로이다. 체스보드의 크기와 나이트가 여행을 시작하는 칸에 따라서 knight's tour가 존재하지 않을 수 도 있다. 만약 knight's tour가 존재하고, 나이트가 tour의 마지막 위치에서 시작 위치로 이동이 가능하다면, 이를 closed knight's tour라고 부르며, 그렇지 않을 때 open knight's tour라고 부른다. 아래 두 문장은 knight's tour에 대한 잘 알려진 사실이다. \(n \times n\) 체스보드에서 \(n\)이 홀수라면 \(n \ge 5\)일때 open knight's tour가 반드시 존재한다.\(n\)이 짝수라면, \(n \g..

INTRODUCTION  PS(problem solving, 본문에서 문제 해결 프로그래밍을 뜻함)에서 bitset을 이용한 최적화는 널리 알려져 있지만, 그렇게 자주 이용되는 것은 아닙니다. 하지만, 몇 가지 경우에서 메모리나 실행 시간을 획기적으로 줄일 수 있는 방법이 되기도 합니다. Reduce Memory  메모리를 줄이는 방법은 생각보다 단순합니다. Boolean array를 이용해야 한다면, 대신 bitset을 이용하는 방법으로 메모리를 1/4정도로 줄이는 것이 가능합니다. 이 방법으로 BOJ 2814번을 sieve만으로 해결하는것이 가능합니다. 또, segment tree leaf node가 0 또는 1만 가진다면, segment tree가 큰 크기를 가지면서 상대적으로 적은 메모리를 가지게..

https://m.blog.naver.com/xyccf777/222572538619 맥OS 에서 AUDIENT 오디언트 ID14 MK2 루프백 설정해서 OBS방송,녹화/디스코드 활용법 맥북에서 오디언트사의 id14 mk2 루프백 설정에 대해서 설명해드리겠습니다. 윈도우와 루프백 설정하는 방... blog.naver.com 위 블로그에 나오는 내용과 거의 동일합니다. 하지만, iD14와 iD4의 채널에 차이가 있기 때문에 LadioCast에서의 설정을 약간 다르게 해주어야 합니다. 먼저 BlackHole과 LadioCast를 다운받아야 합니다. LadioCast의 경우 AppStore에서 다운받아 주세요. / BlackHole의 경우 아래의 링크를 통해 다운받을 수 있습니다. https://existent..

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 =..

INTRODUCTION MLP를 최적화하기 위한 방법으로 가장 잘 알려진 방법은 loss function(or objective function)의 미분을 이용한 함수 최적화 방법과 backpropagation을 이용하는 것이다. 다만, 이런 방법 외에도 GA(Genetic Algorithm)을 이용하여 MLP를 최적화 할 수 있다. - 물론, 이 또한 잘 알려진 방법이다 - 본문에서는 GA를 이용한 간단한 MLP 최적화에 관해 다룰 것이다. 또한, MLP를 이용하는 가장 유명한 예시(or 문제)인 XOR problem에 대해 다룬다. MLP Optimization with GA 어떤 문제를 GA를 통해 해결하기 위해서는 유전자가 어떤 의미를 가지는지 정해주는 것이 가장 중요하다. 필자는 퍼셉트론의 가중..

본문의 내용은 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을..